BAB 7

Genetic Algorithm Optimazation Problems

[KEMBALI KE MENU SEBELUMNYA]

DAFTAR ISI

1. Masalah Optimasi Fuzzy

2. Genetic Fuzzy System ( Individuals )

3. Optimalisasi Kombinatorial Soal

4. Masalah Penjadwalan

5. Masalah Transportasi

6. Desain Jaringan dan Masalah Routing

Genetic Algorithm Optimazation Problems

Penawaran optimasi dengan masalah meminimalkan atau memaksimalkan fungsi dengan beberapa variabel biasanya dikenakan kesetaraan dan / atau kendala ketimpangan. Berdasarkan kesederhanaan, kemudahan operasi, persyaratan minimal dan perspektif paralel dan global, algoritma genetika telah banyak diterapkan dalam berbagai masalah. Sebuah pengantar singkat untuk teknik optimasi genetik dan aplikasi mereka dijelaskan dalam bagian ini, termasuk ladang utama optimasi, seperti optimasi tujuan fuzzy, kombinasi dan multi.

1. Masalah Optimasi Fuzzy

Optimasi Fuzzy menjelaskan masalah optimasi dengan fungsi tujuan kabur dan kendala fuzzy. Hasil yang diperoleh dari metode klasik optimasi yang melibatkan variabel deterministik menunjukkan berbagai shortcomings.In tertentu, efek dari ketidakpastian yang melekat pada informasi masukan sering diabaikan sama sekali atau hanya dibawa ke akununtuk sebuah degree.Theclassical masalah optimasi deterministik terbatas sesuai dengan

find xOPT ∈X with z(x,e) → min

X={x|gi(x,e), hj(x,e)} ­ gi(x,e) ≤ ri         i =1...n

                  and hj(x,e) = 0   j = 1...m .... (7.1)

dianggap di bawah aspek ketidakpastian, dan diperpanjang. Untuk tujuan fungsi z (x, e) optimum solusi xOPT dari set variabel desain X (desain ruang) ditentukan di bawah sesuai dengan kesetaraan kendala Hj (x, e) dan dalam kendala kesetaraan gi (x, e). parameter input seperti parameter geometris, parameter bahan, parameter beban eksternal, parameter kehandalan dan parameter ekonomi disatukan dalam vektor e. Mengingat parameter yang tidak pasti menjadi variabel fuzzy, masalah optimasi deterministik diperpanjang untuk masalah optimasi kabur.

            find xOPT ∈X with  ˜z(x,˜e) →min

 X= {x|˜ gi(x,˜ e),˜ hj(x,˜ e)} ˜gi(x,˜ e) ˜≤˜ ri  i= 1...n

       and ˜ hj(x,˜ e) =0j = 1...m ....... (7.2)

Solusi numerik dari masalah optimasi fuzzy didasarkan pada optimasi α-level.

• Fuzzy Optimization multiobyektif.

Fuzzy masalah optimasi multiobjective dapat dinyatakan dan diselesaikan dengan berbagai cara. Pertimbangkan masalah optimasi formulir,

                                    max/min{G1(x),...,GK(x)}; subject to x ∈ X,  .....(7.3)

dimana Gk, k = 1, ..., K, atau / dan X adalah didefinisikan oleh kabur terms.Then mereka sedang mencari x *, yang memaksimalkan arti Gk di bawah kendala (kabur) X. misalnya, pemrograman linear multiobjective masalah dapat dinyatakan sebagai,

max/min{˜c₁x,...,˜ c_k x}; subject to ˜Ax ≤ ˜ b,... (7.4)

Awalnya fMLP (Fuzzy Programming Mulitobjective Linear) masalah (7.3) diinterpretasikan dengan kabur koefisien dan hubungan ketimpangan fuzzy sebagai beberapa skema penalaran fuzzy, dimana anteseden dari skema sesuai dengan kendala MFLP (Fuzzy Linear Programming multiobjective) masalah dan fakta-fakta skema adalah tujuan dari masalah MFLP.

max/min t-norm(G1(y),...,GK(y)); subject to y ∈ X....(7.5)

• Multiobjective Optimization Under Fuzzy If-then Rules

Sebuah metode optimasi fuzzy interaktif dimasukkan ke dalam algoritma genetika untuk memberikan pengambil keputusan kesempatan untuk menyesuaikan fungsi keanggotaan sesuai dengan informasi yang diberikan oleh pencari genetik saat ini.

Langkah 1: Set awal tingkat keanggotaan referensi (jika sulit untuk menentukan nilai-nilai ini, atur ke 1.0)

Langkah 2: Buat populasi awal yang melibatkan N individu tipe double-string secara acak.

Langkah 3: Hitung fi fitness untuk setiap individu dan menerapkan operator reproduksi berdasarkan fi fitness.

Langkah 4: Masukkan ke dalam populasi saat ini yang sesuai individu dengan solusi optimal untuk setiap fungsi tujuan.

Langkah 5: Operator Crossover Applya sesuai dengan probabilitas cross over Pc.

Langkah 6: Terapkan Operator mutasi sesuai dengan probabilitas mutasi Pm

Langkah 7: Ulangi langkah 3 sampai 6 sampai kondisi terminasi puas. Jika itu adalah puas, menganggap individu dengan maksimal fi fitness sebagai individu yang optimaldan pergi ke langkah 8.

Langkah 8: Jika pembuat keputusan puas dengan nilai saat ini dari fungsi kapal anggota dan fungsi obyektif yang diberikan oleh individu yang optimal saat ini, stop. Otherwise, meminta pembuat keputusan untuk memperbarui tingkat keanggotaan referensi dengan mempertimbangkan nilai-nilai saat ini dari fungsi keanggotaan dan fungsi tujuan dan kembali ke langkah 2.

Jadi dengan algoritma di atas, fuzzy keanggotaan fungsi pemindaian disesuaikan kembali. 

• Genetic Fuzzy System

Dalam arti yang sangat luas, Sistem Fuzzy (FS) adalah sistem berbasis logika-fuzzy mana logika fuzzy dapat digunakan baik sebagai dasar untuk representasi dari berbagai bentuk pengetahuan sistem atau model interaksi dan hubungan antara variabel sistem.

Terlepas dari jenis masalah optimasi, yaitu, mengingat sistem yang dimodelkan atau dikontrol, / tala proses / belajar desain terlibat akan didasarkan pada evolusi. Tiga poin adalah kunci untuk proses genetik:

• populasi solusi potensial

• operator pasangan evolusi / kode, dan

• indeks kinerja.

•    The Population of Potential Solutions

Proses pencarian belajar bekerja pada populasi solusi potensial untuk masalah ini. Individu-individu dari populasi disebut kromosom. pendekatan yang berbeda telah dipertimbangkan, namun yang paling banyak digunakan adalah yang disebut pendekatan Pittsburgh.

• The Evolution Operators /Code

Pertanyaan kedua adalah definisi dari set operator evolusi yang mencari solusi baru yang potensial dan / atau lebih baik. Pencarian mengungkapkan dua aspek yang berbeda: eksploitasi solusi terbaik dan eksplorasi ruang pencarian. Keberhasilan pembelajaran evolusi adalah secara khusus terkait dengan memperoleh keseimbangan yang memadai antara eksplorasi dan eksploitasi yang akhirnya tergantung pada set yang dipilih evolusi operators.

• The Performance Index

Akhirnya, pertanyaan ketiga adalah bahwa merancang sebuah sistem evaluasi yang mampu menghasilkan indeks kinerja yang tepat terkait dengan masing-masing individu dalam populasi dan sedemikian rupa bahwa solusi yang lebih baik akan mendapatkan indeks kinerja kinerja yang lebih tinggi index.
  
2. Soal Desain Keandalan Multiobjektif

Optimalisasi keandalan umumnya diterapkan pada masalah komunikasi dan transportasi. Keandalan sistem didefinisikan sebagai probabilitas bahwa sistem telah beroperasi dengan sebaik-baiknya selama interval waktu tertentu dalam kondisi tertentu.

• Desain Keandalan Jaringan

Desain keandalan jaringan didasarkan pada pembagian sumber daya perangkat keras dan perangkat lunak yang mahal dan menyediakan akses ke sistem server utama dari lokasi yang jauh. Langkah penting dari proses perancangan jaringan adalah menemukan tata letak komponen terbaik untuk mengoptimalkan kriteria kinerja tertentu seperti biaya, keandalan, delay transmisi atau throughput. Keandalan desain jaringan adalah sebagai berikut:

• Semua keandalan jaringan terminal - probabilitas bahwa setiap simpul di jaringan terhubung satu sama lain

• Sumber Sink Network Reliability - probabilitas bahwa sumber terhubung dengan sink, sehingga node sumber di jaringan dapat berkomunikasi dengan node sink selama waktu misi tertentu. 

• Deskripsi Masalah

Desain optimal dari semua keandalan jaringan terminal didefinisikan sebagai berikut:

n adalah jumlah node

xij ∈ {0,1} adalah variabel keputusan yang mewakili tepi antara node i dan j

x = {x12, x13, ..., xn-1, n} arsitektur isatopologi dari desain jaringan

x * adalah solusi terbaik yang ditemukan sejauh ini

p adalah keandalan tepi untuk semua sisi

q tidak dapat dipercaya untuk semua sisi (p + q = 1)

R (x) adalah semua keandalan terminal dari desain jaringan x

Rmin adalah persyaratan keandalan jaringan

Ru (x) adalah batas atas keandalan jaringan kandidat

cij adalah biaya tepi antara node i dan j

cmax adalah nilai maksimum cij

δ memiliki nilai 1 jika R (x) <Rmin, yang lain, memiliki nilai 0

E 'adalah satu set tepi operasional (E' ⊆ E)

Ω adalah semua keadaan operasional.

Desain jaringan yang optimal direpresentasikan sebagai berikut:

• Pendekatan Algoritma Genetika

Notasi berikut digunakan untuk menggambarkan desain jaringan yang optimal, yang memungkinkan

tepi dipilih dari pilihan tepi yang berbeda:

k adalah jumlah pilihan untuk koneksi tepi

t adalah pilihan antara node

xij adalah pilihan tepi untuk tepi antara node i dan j

p (xij) adalah pilihan desain keandalan dan

c (xij) adalah satuan biaya dari pilihan tepi

Representasi: Karena setiap desain jaringan x mudah dibentuk menjadi vektor bilangan bulat, maka dapat digunakan sebagai kromosom untuk algoritma genetika.

Kebugaran: Fungsi penyimpanan adalah untuk menemukan arsitektur jaringan dengan biaya minimum yang memenuhi atau melampaui keandalan jaringan yang telah ditentukan sebelumnya, Rmin. 

dimana,
Zp (x) –penalizedcot

Z (x) –Unpenalizedcost

Z (x *) - biaya solusi layak terbaik dalam populasi

rp-penalty rate popsize-populationsize

gen-jumlah generasi

Algoritma: Algoritma keseluruhan untuk meminimalkan biaya dari jaringan adalah sebagai berikut:

Langkah 1: Tetapkan parameter, ukuran populasi (popsize), persentase populasi bermutasi (pm1), mutasi rate (pm2), tingkat hukuman (rp), generasi maksimum (maxgen) dan inisialisasi jumlah generasigen = 0.

Langkah 2: Inisialisasi a) Secara acak menghasilkan populasi awal

b) Kirimkan populasi awal untuk perhitungan reliabilitas

c) Kirimkan populasi awal ke fungsi perhitungan biaya (kesesuaian). Jika kromosomexist tidak layak, mereka akan dikenakan sanksi.

d) Uji solusi awal terbaik. Jika tidak ada kromosom yang layak dilakukan, kromosom terbaik yang tidak layak dicatat.

Langkah 3: Seleksi a) Masukkan kromosom terbaik ke populasi baru

b) Pilih dua kromosom kandidat yang berbeda dari populasi saat ini dengan proses seleksi berbasis peringkat.
Langkah 4: Lakukan Crossover. Seragam crossoveris dilakukan.

Langkah 5: Lakukan Mutasi. Setelah crossover sekali anak diciptakan, lalu mutasikan saja. Langkah 6: Periksa jumlah anak. Jika n <popsize-1, goto langkah 3; lain goto langkah 6, dimana n mewakili jumlah anak baru.

Langkah 7: Bentuk populasi baru. Ganti orang tua dengan anak yang sudah tercipta.
Langkah 8: Evaluasi a) Kirimkan populasi baru ke fungsi perhitungan reliabilitas

b) Hitung fungsi kebugaran untuk setiap kromosom pada populasi baru. Jika kromosomexist tidak layak, mereka akan dikenakan sanksi

Langkah 9: Periksa kromosom baru terbaik. Simpan kromosom baru terbaik; Jika tidak ada kromosom yang layak, maka kromosom terbaik yang tidak layak dicatat.

Langkah 10: Periksa kondisi terminating. Jika gen <maxgen, gen = gen + 1, dan goto langkah 3 untuk generasi berikutnya. Jika gen = maxgen, maka hentikan.

Perhitungan Reliabilitas: Algoritma pelacakan kembali digunakan untuk menghitung ketidakandalan sistem yang tepat, 1-R (x), untuk masalah karena ukuran komputasi yang dapat ditimbang.
Langkah 1: Inisialisasi semua sisi sebagai gratis dan buat tumpukan S yang kosong diinisialisasi.

Langkah 2: Buatlah potongan lucu yang modis

a) Temukan satu set tepi bebas yang bersamaan dengan semua tepi yang tidak beroperasi akan membentuk jaringan yang terpotong.

b) Tandai semua tepi yang ditemukan pada langkah di atas tidak aktif dan tambahkan ke tumpukan.

c) Sekarang tumpukan mewakili potongan potong yang dimodifikasi; tambahkan probabilitasnya ke jumlah kumulatif.

Langkah 3: Proses backtrack.

a) Jika tumpukan kosong, pindahlah ke langkah 4, yang lain, goto langkah 3- (b) di bawah ini.

b) Ambil tepi dari atas tumpukan.

c) Jika tepi tidak berfungsi dan jika saat membuatnya beroperasi, spanningtree dari operativeedges ada, tandai secara gratis dan goto step 3- (a).

d) Jika tepi tidak beroperasi dan kondisi yang diuji pada langkah 3- (c) tidak tahan, tandai operasinya, pasang kembali ke tumpukan, dan lanjutkan ke langkah 2.

e) Jika tepinya beroperasi, tandai secara gratis dan lanjutkan ke langkah 3- (a).

Langkah 4: Kembalikan jaringan yang tidak dapat diandalkan dan akhiri prosedurnya.
Dengan demikian masalah disain keandalan jaringan dapat diselesaikan secara efisien dengan menggunakan pendekatan algoritma genetika.

• Desain Keandalan Bicriteria

Permasalahannya adalah variasi dari masalah alokasi yang optimal, yang diformulasikan sebagai program bilangan bulat anon-linearmixed sebagai berikut:

dimana,

jumlah komponen redundant dalam subsistem i

xi-tingkat komponenabilitas untuk subsistem ke-i

f1 (m, x) -memastikan sistem dengan komponen-komponen dan reliabilitas komponen x

f2 (m, x) - biaya total sistem dengan alokasi komponen m dan reliabilitas komponen x

vi-produk berat dan volume per elemen dalam subsistem i

wi-bobot masing-masing komponen dalam subsistem i

dan C (xi) - masing komponen dengan reliabilitas xi pada subsistem i diperoleh sebagai berikut:

dimana, αi dan β areconstants mewakili karakteristik fisik dari komponen yang ada dalam subsistem i, dan PL adalah waktu operasi dimana komponen tidak boleh gagal.

• Pendekatan Algoritma Genetika

Kesesuaian kromosom dihitung dengan metode pemeringkatan sebagai berikut:
Evaluasi Kebugaran

Langkah 1: Hitung setiap nilai obyektif untuk setiap kromosom

Langkah 2: Kromosom digolongkan berdasarkan nilai fungsi obyektifnya dan memperoleh orderri (vk) .ri (vk) adalah nilai rangking dari nilai objektivitas dari kromosom vk dan diperoleh dengan menetapkan nilai 1 pada nilai fungsi objektif terbaik dan popsize pada fungsi obyektif terburuk dari populasi sekarang.

Jika fungsi objektif dimaksimalkan, maka,

ri (vk) - seperti 1 pada objectivevalue terbesar

popsize-pada nilai fungsi objektif terkecil

Jika fungsi objektif diminimalkan, maka,

ri (vk) -setiap sebagai nilai obyektif terkecil

popsize-pada nilai fungsi tujuan terbesar

Langkah 3: Hitunglah nilai kesesuaian dengan persamaan berikut:

Dimana, Q adalah fungsi objektifnya.

Hitung fungsi eval evaluasi (vk), dan pilih kromosom diantara orang tua dan keturunan yang lebih unggul dari yang lain. Jumlah yang akan dipilih adalah popsize.

Crossover
Operator crossover aritmetika digunakan, yang merupakan kombinasi linear dua kromosom.
 

Mutasi
Mutasi seragam dilakukan disini Operator ini memastikan bahwa GA dapat mencari solusi secara bebas. Dengan demikian, masalah desain jaringan yang menyangkut keandalan sistem atau kendala memiliki banyak aplikasi di bidang telekomunikasi, jaringan komputer dan domain seperti jaringan listrik, gas dan selokan.

3. Optimalisasi Kombinatorial Soal

Optimalisasi kombinatorial adalah cabang optimasi dalam matematika terapan dan ilmu komputer, terkait dengan riset operasi, teori algoritma dan teori kompleksitas komputasi yang berada pada persimpangan beberapa bidang, termasuk kecerdasan buatan, matematika dan rekayasa perangkat lunak.

Definisi Informal: Domain optimasi kombinatorial adalah masalah optimasi dimana rangkaian solusi layak diskrit atau dapat dikurangi menjadi diskrit, dan tujuannya adalah untuk menemukan solusi terbaik.
Definisi formal: Contoh masalah optimasi kombinatorial dapat digambarkan secara formal sebagai tuple (X, P, Y, f, extr) dimana

• X adalah ruang solusi (dimana f dan P didefinisikan)

• P adalah predikat kelayakan.

• Y adalah seperangkat solusi yang layak.

• f adalah fungsi tujuan.

• Ekstra adalah ekstrem (biasanya min atau max).

• Model Integer Linier

Meskipun beberapa penelitian berpusat pada pendekatan terhadap masalah di mana beberapa atau semua fungsi bersifat nonlinier, sebagian besar penelitian sampai saat ini hanya mencakup kasus linier. Model bilangan bulat linier secara umum adalah

 

• Aplikasi Optimal Kombinatorial

Kami mendeskripsikan beberapa model pengoptimalan kombinatorial klasik untuk memberikan gambaran umum keragaman dan fleksibilitas bidang ini dan untuk menunjukkan bahwa solusi dari kasus dunia nyata yang besar mengenai masalah tersebut memerlukan metode solusi untuk memanfaatkan struktur matematika khusus dari aplikasi spesifik.

• Masalah Knapsack

Misalkan seseorang ingin mengisi ransel yang dapat menahan berat total W dengan beberapa kombinasi dari bahan kimia yang mungkin terjadi dengan berat dan beratanya sehingga nilai barang yang dimasukkan ke dalam ransel dimaksimalkan.

• Masalah Jaringan dan Grafik

Banyak masalah optimasi dapat ditunjukkan oleh jaringan dimana jaringan (atau grafik) didefinisikan oleh node dan oleh busur yang menghubungkan node tersebut. Banyak masalah praktis yang dihadapi oleh jaringan fisik, jalan raya, sistem rails, jaringan komunikasi, dan sirkuit terpadu.

• Jaringan Ruang-Waktu Sering Digunakan dalam Aplikasi Penjadwalan

Disini seseorang ingin memenuhi permintaan spesifik pada berbagai titik waktu. Untuk memodelkan masalah ini, node yang berbeda mewakili entitas yang sama pada titik waktu yang berbeda.

• Masalah Penjadwalan, yang berbasis Aturan

Ada banyak masalah dalam hal ini adalah mungkin untuk menuliskan semua batasan secara matematis "bersih". Masalah seperti itu sering muncul dalam penjadwalan dimana ada banyak pembatasan tenaga kerja, preferensi penjadwalan perusahaan dan peraturan lainnya yang terkait dengan apa yang merupakan "jadwal yang layak."

Masalah optimasi adalah masalah dalam menemukan kumpulan kolom terbaik, yang memenuhi batasan ini.

Terlepas dari abwasiscussed, itu juga bisa digunakan untuk memecahkan:

• Traveling salesman problem

• Minimum spanning tree problem

• Pemrograman linier

• Delapan teka-teki ratu

• Teknik Solusi untuk Pemrograman Integer

Memecahkan masalah optimasi kombinatorial, yaitu menemukan solusi optimal untuk masalah semacam itu, bisa menjadi tugas yang sulit. Kesulitan muncul dari kenyataan bahwa tidak seperti pemrograman linier, misalnya, yang wilayahnya layak adalah satu cembung, dalam masalah kombinatorial, seseorang harus mencari kisi titik layak atau, dalam kasus gabungan-integer, satu set garis setengah yang terputus-putus atau segmen garis untuk menemukan solusi optimal.

• Metode

Metode penelitian heuristik (metaheuristicalgorithms) asthoselistedbelowhavebeen digunakan untuk mengatasi masalah optimasi kombinatorial.

• Pencarian lokal

• Simulated annealing

• Quantum annealing

• GRASP

• kecerdasan swarm

• pencarian tabu

• Algoritma genetika

• Algoritma Genetika Berbasis Quantum

• Ant koloni optimasi, pencarian Reaktif

• Algoritma Genetika Berbasis Quantum untuk Memecahkan Masalah N-Queens

Algoritma genetika (GAs) adalah pendekatan yang mendekati yang telah membuktikan efisiensi kinerjanya pada masalah optimalisasi kombinatorial. Algoritma genetika adalah biologisDarwinianprincipaluntukmengoptimalisasifungsi yangdikenal.

Masalah N-Queens adalah masalah kecerdasan artifisial klasik. Ini adalah kasus umum masalah 8-Queens. Masalah optimasi kombinatorial ini telah dipelajari selama lebih dari satu abad.

Komputasi Quantum

Pada awal tahun 80-an, Richard Feynman mengamati bahwa beberapa efek mekanika kuantum tertentu tidak dapat disimulasikan dengan cermat pada komputer digital.

N-Queens Problem Solving

GA konvensional beroperasi pada satu set individu (kromosom) membentuk populasi. Agar lebih representatif populasi ini harus mengandung sejumlah kromosom.

Quantum Genetic Algorithm (QGA).

QGA adalah GA dengan solusi pengkodean kuantum. Representasi ini akan mengurangi waktu komputasi dengan meningkatkan jumlah kromosom. Apalagi kami yakin hal itu akan memberikan solusi global yang lebih baik.

Pemodelan Solusi

Setiap ratu di kotak pemeriksa bisa mencapai kotak lain yang berada pada garis horisontal, vertikal, dan diagonal yang sama. Jadi ada paling banyak satu ratu di setiap garis horizontal, paling banyak satu ratu di setiap garis vertikal, dan paling banyak satu ratu di masing-masing garis diagonal 4n-2.

Fungsi kebugaran

Kekentalanan dari jumlah suara yang sama dari yang ada pada batas waktu. Ketepatan konfigurasi sama dengan jumlah semua hukuman ratu yang dibagi dua (menghapus redundancycounting) . Contoh kualitas larutan yang disajikan pada Gambar 7.2 adalah 0 dan kecocokan larutan matriks pada Gambar 7.3 adalah 8.

Gambar 7.2 Matriks solusi dari masalah 4-Queens

Gambar 7.3 Matriks solusi yang buruk dari masalah 4-Queens

Representasi kuantum

Representasi solusi yang diberikan di atas dapat membuat representasi ruang pencarian dalam algoritma genetika sangat besar. Karena itu, kami mengusulkan representasi lain dari solusi (kromosom).

Gambar 7.4 Matriks solusi kuantum

Gambar 7.5 Interferensi kuantum

 

Gambar 7.6 Quantum cross-over

 

Gambar 7.7 mutasi kuantum

4. Masalah Penjadwalan

Dalam pengaturan manufaktur yang kompleks saat ini, dengan banyak lini produk, masing-masing memerlukan banyak langkah dan mesin yang berbeda untuk menyelesaikannya, pembuat keputusan untuk pabrik manufaktur harus menemukan cara untuk mengelola sumber daya dengan sukses agar menghasilkan produk dengan cara yang paling efisien.

Berbagai masalah penjadwalan meliputi:

- Penjadwalan job shop

- Multiprocessorscheduling

- Penjadwalan multitask

- Penjadwalan Mesin Paralel

- Penjadwalan Job Group

- Penjadwalan proyek sumber daya terbatas

- Dynamic task scheduling dan sebagainya.

• Algoritma Genetika untuk Masalah Penjadwalan Job Shop (JSSP)

Penjadwalan, terutama penjadwalan job shop, telah lama belajar. Karena sifat NP-Hard-nya, belum ditemukan pemecah masalah global untuk masalah seperti ini. Baru-baru ini, beberapa meta-heuristik seperti Simulated Annealing (SA), Taboo Search (TS), dan Genetic Algorithms (GA) telah diimplementasikan sebagai metode murni dan hibrida dengan metode yang berbeda, dimana metode hibrida lebih unggul dari yang asli.

• Jenis Jadwal

Jadwal dapat diklasifikasikan menjadi satu dari tiga jenis jadwal berikut:
• Jadwal semi-aktif: Hal ini dimungkinkan dilakukan pada operasi sebelum operasi sedini mungkin. Dalam jadwal semi aktif, tidak ada operasi yang bisa dimulai lebih awal tanpa mengubah urutan pemrosesan.
• Jadwal aktif: Jadwal yang layak ini adalah jadwal di mana tidak ada operasi yang bisa dimulai lebih awal tanpa menunda operasi lain atau melanggar precedenceconstraint sebelumnya. Jadwal aktif juga merupakan jadwal semi aktif. Jadwal yang optimal selalu aktif, sehingga ruang pencarian bisa dibatasi secara aman dengan rangkaian semua jadwal aktif.

• Non-penundaan: Hal-hal yang tidak dapat dipungkiri ini terjadi pada saat penjahat tidak dipelihara saat bisa mulai memproses beberapa operasi. Jadwal non-delay selalu aktif dan karenanya juga harus semi aktif.

• Pendekatan Algoritma Genetika

Algoritma genetika (GA) meniru evolusi dan peningkatan kehidupan melalui reproduksi, di mana masing-masing individu mengumpulkan informasi genetiknya sendiri untuk membangun yang baru yang disesuaikan dengan lingkungan dengan tingkat kelangsungan hidup yang lebih tinggi. Inilah salah satu gagasan utama di balik algoritma genetika dan pemrograman genetika.

Gambar 7.8 menunjukkan siklus generik GA dimana individu terbaik terus dipilih dan dioperasikan dengan crossover dan mutasi. Setelah beberapa generasi, populasi bertemu kembali dengan solusi yang dilakukan.

• Algoritma Genetika di JSSP

Jadwal dihasilkan dengan cara tertentu dimana kromosom akan layak dilakukan setelah melakukan operator genetika. Manajemen keputusan di JSSP mendistribusikan pekerjaan untuk setiap mesin, memilih satu tugas di antara alternatif lain sehingga memiliki kemampuan yang lebih baik.

Masalah utama dengan pendekatan ini adalah sebagai berikut:

• efek mengganggu dari crossoveroperator,

• Konvergensi dewasa sebelum waktunya untuk beberapa menit lokal yang membutakan sistem untuk menemukan yang global,

• Akhirnya meningkatkan ketidakmampuan operator genetik untuk mengubah solusi dalam sebuah alasan,
• Kurangnya pendakian bukit di GA.

Gambar 7.9 Urutan keputusan di JSSP

Tabel 7.1 Hasil yang diperoleh dari algoritma genetika

5. Masalah Transportasi

Masalah transportasi meliputi penentuan pola transportasi optimum, analisis masalah penjadwalan produksi termasuk pengendalian persediaan, masalah pengiriman barang dan beberapa masalah penugasan lainnya.

• Algoritma Genetika dalam Memecahkan Transportasi

Masalah alokasi lokasi transportasi adalah masalah di mana kedua sumber asam yang optimal dan jumlah pengiriman yang optimal dari sumber asam dapat ditemukan.

• Deskripsi Masalah

Meskipun masalah transportasi umum hanya mengacu pada "sumber" dan "tujuan," untuk kejelasan, algoritme akan memecahkan contoh tertentu dari masalah lokasi transportasi, yaitu mengidentifikasi lokasi optimal dari pembangkit listrik baru untuk memasok yang baru (atau masa depan) kebutuhan energi dari sejumlah kota. Tujuan dari masalah ini adalah untuk meminimalkan biaya distribusi daya total.

Bentuk matematika dari masalah dapat ditulis sebagai,

Dimana
φ = biaya transportasi per satuan jumlah per satuan jarak

δij = jarak dari sumber i ke tujuan j

vij = jumlah yang dipasok dari sumber i ke tujuan j

n = jumlah tanaman

m = jumlah kota

xi, yi = koordinat X & Y dari sumber i

x j, yj = koordinat X & Y dari tujuan j

dj = permintaan dari tujuan

ci = kapasitas sumber

• Pendekatan Algoritma Genetika

Metode Two-Phase diimplementasikan untuk memecahkan masalah alokasi lokasi. Tahap 1 melibatkan teknik Algoritma Genetika, yang digunakan untuk meminimalkan biaya transportasi dengan memvariasikan lokasi sumber. Tahap 2 mencakup teknik Pemrograman Linier untuk mengalokasikan kekuatan dari sumber ke tujuan sesuai dengan kendala.

Tahap 1

Langkah 1: Thelocationsanddemandsforeach kota; thelowerand upperlimits untuk lokasi tanaman; kapasitas pabrik; populasi; dan jumlah generasi yang ditentukan. Batas atas dan bawah digunakan untuk membuat populasi acak awal dari lokasi sumber.

Langkah 2: Fungsi tujuan (7.15) dievaluasi untuk populasi acak lokasi tanaman dengan memanggil subrutin fase 2, yang secara optimal mengalokasikan daya dari tanaman ke titik permintaan, dan memastikan bahwa kendala tersebut dapat dipenuhi.

Langkah 3: Lokasi X dan Y dari semua tanaman dari populasi awal dikonversi menjadi basis 10 bilangan bulat dan dikonversi ke bentuk binernya. Dari nilai fungsi objektif, probabilitas dan probabilitas kumulatif untuk setiap individu dalam populasi dihitung.

Langkah 4: Pemilihan orang tua dilakukan atas dasar fungsi kebugaran. Individu yang memiliki nilai kesesuaian lebih tinggi dipilih lebih sering. Semakin besar nilai kesesuaian individu, semakin besar kemungkinan individu tersebut akan dipilih untuk rekombinasi. Pemilihan orang tua kawin adalah pilihan roulette wheel, dimana probabilitas untuk setiap individu, i, dihitung. Orang tua kemudian dipilih secara acak, berdasarkan probabilitas ini.

Langkah 5: Theparentsthusselectedaremadetomate menggunakan metode two-pointcrossover. Keturunan yang diperoleh membentuk populasi baru lokasi tanaman. Versi biner populasi baru diubah menjadi basis-10 bilangan bulat dan kemudian ke nilai sebenarnya.

Langkah 6: Langkah 2-5 dilakukan dengan mengulang angka yang telah ditentukan sebelumnya.

Langkah 7: Di orderto mempertahankan keragaman dalam populasi, dua operator, yaitu mutasi dan elitisme disertakan. Mutasi adalah perubahan acak gen dari 0 sampai 1 (atau 1 sampai 0). Elitisme adalah prosedur dimana individu terlemah dari populasi saat ini digantikan oleh individu paling cepat dari populasi sebelumnya. Mutasi, dan operator elitisme menawarkan kesempatan untuk materi genetik baru diperkenalkan ke populasi.

Langkah 8: Biaya akhir dan akhir (X dan Y) lokasi tanaman dilaporkan.

Tahap 2

Pada Tahap 2, lokasi acak tanaman diterima dari Tahap 1 dan dipecahkan sebagai masalah transportasi linier dengan menggunakan algoritma simpleks. Algoritma Simplex mengoptimalkan biaya untuk alokasi daya dari pabrik ke kota-kota, seminimal mungkin. Nilai biaya optimal, yaitu nilai fungsi objektif dalam Algoritma Genetika, dilewatkan kembali ke Tahap 1.

• Genetic Genetic Algorithm (RCGA) untuk Pemrograman Linear Integer dalam Masalah

Transportasi Produksi dengan Biaya Transportasi Fleksibel

Di antara berbagai bentuk masalah pemrograman linier, jenis yang populer dan penting adalah masalah transportasi tradisional, di mana tujuannya adalah untuk meminimalkan biaya transportasi dari berbagai jumlah komoditas homogen tunggal dari tempat yang berbeda dengan tujuan lainnya. Biasanya, masalah transporasi transporasi (TP) adalah minimisasi

Beberapa perusahaan manufaktur dipaksakan untuk terus menjalankan bisnisnya secara simultan di bawah kendali mereka sendiri:

1. Manufaktur dan Pemasaran komoditi.

2. Menjual di showroom yang berbeda yang berada di berbagai pasar / lokasi penting.

3. Transportasi komoditas dari berbagai pabrik ke ruang pamer yang berbeda.
Akibatnya, tujuan keseluruhan perusahaan manufaktur adalah memaksimalkan sistem penilaian yang mengacu pada keputusan pemberian hak suara yang berbeda-beda seperti kapasitas pabrik yang berbeda.

Algoritma genetika (GA) adalah metode pencarian dan optimasi stokastik terkomputerisasi yang bekerja dengan meniru prinsip evolusioner dan pemrosesan kromosom dalam genetika alami.

Model transportasi produksi yang realistis dikembangkan dengan asumsi bahwa perusahaan sedang menjalani kegiatan berikut:

(i)                  Memproduksi produk homogen tunggal yang berbeda (terletak di tempat yang berbeda dengan biaya bahan baku yang berbeda, biaya produksi dan biaya pemasaran per unit).

(ii)                Mengangkut produk ke lokasi yang berbeda-beda (dengan harga berbeda per unit). Biaya pengangkutan unit dari sumber tertentu ke tujuan tertentu tidak dapat diperbaiki, namun dapat dilipat. Umumnya, unit yang ditranskripsikan dari mana pun yang memenuhi syarat, harus dikirim ulang, jika biaya transportasi dikenai biaya per unit.

(iii)               Menjual produk-produk yang berbeda sesuai dengan tujuan perusahaan di perusahaan adalah memaksimalkan keuntungan total.

• Asumsi dan Notasi

Asumsi dan notasi berikut digunakan untuk mengembangkan model yang diusulkan.

(i)                  Perusahaan memiliki pabrik pabrik Fi (menghasilkan produk homogen) dengan kapasitas ai (i = 1,2, ..., m) dan ada ruang pamer di pasar Mj dengan permintaan (persyaratan) bj (j = 1,2 , ..., n).

(ii)                Biaya transportasi konstan untuk kendaraan pengangkut dengan kapasitas tertentu (walaupun biaya yang dikeluarkan tidak sampai kapasitas yang memadai dari kendaraan transpor dengan kuantitas tertentu).

(iii)               Kapasitas kendaraan pengangkut adalah unit K.

(iv)               xij mewakili kuantitas yang tidak diketahui untuk diangkut dari pabrik Fi ke pasar Mj.

(v)                Cij menjadi biaya transportasi untuk kendaraan angkut muatan penuh dan C'ij menjadi biaya transportasi per unit dari Fi ke Mj.

(vi)               Uij menjadi titik jeda atas, beberapa unit kurang dari K tapi lebih dari Uij, biaya transportasi untuk keseluruhan kuantitas adalah Cij. Oleh karena itu, Uij =? Cij / C'ij? <K di mana Cij / C'ij? Adalah nilai bilangan bulat terbesar yang kurang dari atau sama dengan Cij / C'ij.

(vii)             Cri dan Cpi menjadi bahan baku dan biaya produksi per unit di pabrik Fi (i = 1,2, ...., m) perusahaan.

(viii)           pj adalah harga jual per unit di pasar (1, 2, ...,) Mj (j = 1,2, ... n).

• Perumusan Model Masalah

Total Pendapatan TR dari perusahaan diberikan oleh,

dan total biaya produksi termasuk biaya bahan baku,

Biaya transportasi

• Implementasi GA

Prinsip kerja dari GA adalah sebagai berikut:

Langkah-1: Menginisialisasi parameter-parameter dari Algoritma Genetic dan perbedaan parameter transportasi.
Langkah-2: t = 0 [t mewakili jumlah currentgeneration.]

Langkah-3: Inisialisasi P (t) [P (t) mewakili populasi pada generasi ke-t]

Langkah ke-4: Evaluasi P (t).

Langkah-5: Temukan hasil terbaik dari P (t).

Langkah-6: t = t +1.

Langkah-7: Jika (t> jumlah generasi maksimum) masuk ke langkah ke-14

Langkah-8: Pilih P (t) dari P (t -1) dengan proses seleksi seperti pemilihan roulette wheel, pemilihan tournamen, pemilihan peringkat dll.

Langkah-9: Alter P (t) dengan operasi crossover dan mutasi.

Langkah-10: Evaluasi P (t).

Langkah-11: Temukan hasil terbaik dari P (t).

Langkah ke-12: Bandingkan hasil terbaik dari P (t) dan P (t-1) dan simpan yang terbaik.

Langkah ke-13: Masuk ke langkah ke-6.

Langkah ke-14: Cetak hasil terbaik.

Langkah ke-15: Berhenti.

• Representasi Kromosom

Untuk aplikasi GA yang tepat, perancangan representasi kromosom yang tepat untuk pemecahan masalah merupakan tugas penting.

• Fungsi Evaluasi

Setelah mendapatkan banyak solusi potensial, kita perlu melihat seberapa bagus mereka. Oleh karena itu, kita harus menghitung kecocokan masing-masing kromosom.

6. Desain Jaringan dan Masalah Routing

Keragaman besar pertanyaan dan masalah yang berasal dari tugas perencanaan dan perancangan jaringan hari ini memerlukan sejumlah besar algoritma, yang masing-masing mengkhususkan pada masalah spesifik dengan batasan spesifik.

• Perencanaan Jaringan Optik Pasif

• Deskripsi Masalah

Passive Optical Networks (PON) menyediakan cara untuk secara bertahap mengenalkan teknologi optik serat ke dalam jaringan akses sementara masih menggunakan jalur kabel atau sistem coax-cable. PON dapat diimplementasikan di beberapa topologi. Salah satu konfigurasi dari kecaman itu adalah perusakan di bawah Beban Praktis (OLT) di kantor pusat dapat dilihat sebagai akar dan Unit Jaringan Optik (ONU) sebagai daun pohon.

• Pendekatan Algoritma Genetika

Algoritma genetik sederhana diterapkan pada desain jaringan optik pasif. Pengkodean genetik dari beberapa alternatif tertentu dari pohon Steiner terdiri dari serangkaian nilai integratif dengan data kesehatan yang berbeda dalam kandungannya.

• Perencanaan Jaringan Switched Packet

• Deskripsi Masalah

Perancangan jaringan packet switched membutuhkan solusi dari berbagai jenis masalah, mis. penempatan node dan dimensi link, optimasi routing, spesifikasi server, atau penugasan alamat. Pada makalah kami, kami hanya mempertimbangkan aspek topologi link dan optimasi routing. 

• Desain Topologi Optimal untuk Semua Jaringan Terminal

Tahap desain ini disebut "Network Topological Optimization". Dalam masalah desain jaringan topologi, perhatian utama adalah merancang jaringan, yang beroperasi secara efektif dan tanpa gangguan dengan adanya kegagalan komponen. Reliabilitas berkaitan dengan kemampuan jaringan untuk melakukan operasi jaringan yang diinginkan.

• Deskripsi Masalah

Berdasarkan asumsi berikut:

(1) lokasi setiap node jaringan diperbaiki dan diberikan,

(2) masing-masing dan biaya yang ditentukan dan diketahui, dimana adalah thecostoflink di jaringan antara node i dan j, dan p, q adalah reliabilitas link dan tidak dapat diandalkan (p + q = 1),

(3) setiap link bersifat bi-directional,

(4) tidak ada redundantlink dalam jaringan,

(5) probabilitas kegagalan suatu hubungan adalah independen terhadap keadaan dari hubungan lainnya,

• Pendekatan Algoritma Genetika

GA dikembangkan sebagai metodologi solusi untuk topologi optimasi jaringan dengan batasan reliabilitas. Di GA, ruang pencarian terdiri dari solusi yang mungkin untuk masalah tersebut; masing-masing diwakili sebagai infrastruktur yang disebut sebagai kromosom. Setiap kromosom memiliki nilai fungsi tujuan terkait, yang disebut nilai ketahanan. Kromosom adalah onethat yang memiliki nilai kesesuaian tinggi. Satu set kromosom bersama dengan nilai kesesuaiannya yang terkait disebut populasi

Karakteristik berikut dikontrol secara sistematis.

• Probabilitas Arc antara [0, 1], yang menentukan adanya busur antar node, dipilih.

• Nilai keandalan sistem yang ada dalam jaringan dihubungkan dengan simulasi Monte Carlo.

• Nilai probabilitas keberadaan busur dan nilai reliabilitas jaringan yang sesuai dikompilasi.

Tujuannya adalah untuk menentukan nilai investasi yang sangat mungkin, yang merupakan jaringan yang sangat andal.

 

Read More