BAB 11 :Pengenalan Optimasi Partikel Swarm dan Ant Colony Optimization  

[KEMBALI KE MENU SEBELUMNYA]

DAFTAR ISI

1. Optimisme Partikel Swarm

2. Ant Colony Optimization

Genetic Algorithm Optimazation Problems

Optimalisasi pada proses optimal untuk mengatasi masalah yang menjadi pertimbangan utama. Optimalisasi Optimal dan Ant Colony Optimization mencapai solusi optimal untuk masalah pencarian dengan menggunakan perilaku sosial organisme hidup. Pengoptimalan partikel partikel adalah bentuk kecerdasan swarm dan pengoptimalan koloni Ant adalah metaheuristik berbasis populasi yang dapat digunakan untuk mengatasi masalah hidrodinamika sehingga dapat memecahkan masalah optimasi.

1. Optimisme Partikel Swarm [kembali]

Partikel swarm optimization (PSO) adalah teknik optimasi stokastik berbasis populasi yang dikembangkan oleh Dr. Eberhart dan Dr. Kennedy pada tahun 1995, terinspirasi oleh perilaku sosial aliran burung atau sekolah ikan. PSO memiliki banyak kesamaan dengan teknik komputasi evolusioner seperti Genetic Algorithms (GA). Sistem ini diinisialisasi dengan populasi solusi acak dan pencarian optima dengan memperbarui generasi.
Pada PSO, partikel-partikel tersebut, disebut partikel, melewati ruang masalah dengan mengikuti partikel optimum saat ini.
Partikel swarm optimasi telah digunakan untuk pendekatan yang dapat digunakan di berbagai aplikasi, serta untuk aplikasi tertentu difokuskan pada persyaratan tertentu.
11.2.1 Latar Belakang Optimasi Swarm Partikel
Partikel swarm optimization (PSO) adalah bentuk kecerdasan swarm dan terinspirasi oleh aliran burung, bulu tangkis dan serangga.

Perhatikan Gambar 11.1 dan bayangkan segerombolan serangga atau sekolah ikan. Jika seseorang melihat jalur yang diinginkan untuk dikunjungi (mis., Untuk makanan, perlindungan, dll.), Kawanan lainnya akan dapat mengikuti dengan cepat meskipun mereka berada di sisi yang berlawanan dari kawanan.
Ada dua cara utama yang harus dilakukan:
• terbaik global yang diketahui semua dan segera diperbarui saat posisi terbaik baru ditemukan oleh partikel manapun di kawanan
• "lingkungan" paling baik dimana masing-masing partikel segera berkomunikasi dengan subset kawanan tentang posisi terbaik
Setiap partikel melacak koordinatnya di ruang masalah yang dikaitkan dengan solusi terbaik (kesesuaian) yang telah dicapai sejauh ini. (Nilai ketahanan juga disimpan.) Nilai ini disebut pbest. Nilai "terbaik" lain yang dilacak oleh optimizer partikel adalah nilai terbaik, sejauh ini diperoleh partikel partikel tetangga. Lokasi ini disebut lbest.
11.2.2 Pengoperasian Optimasi Partikel Swarm
Sebaiknya perhatikan bagian-bagian yang ada di bawah batas-batas yang dicari untuk optimum. Setiap partikel dicirikan oleh,
Vektor posisi ..... xi (t)
Vektor kecepatan ...... vi (t)
seperti ditunjukkan pada Gambar 11.2.
Selama proses berlangsung, masing-masing partikel memiliki pengetahuan masing-masing, yaitu, best-so-far terbaiknya di posisi dan pengetahuan sosial, yang paling baik dari tetangganya yang terbaik ditunjukkan pada Gambar 11.3.
Update kecepatan didasarkan pada parameter seperti yang ditunjukkan pada Gambar 11.4.
Sekarang, melakukan update posisi,
Proses update posisi seperti ditunjukkan pada Gambar 11.5
Proses di atas dibahas berulang-ulang untuk setiap partikel evry yang dipertimbangkan dalam perhitungan dan solusi optimal terbaik diperoleh.
11.2.3 Arus Dasar Pengoptimalan Partikel Swarm
Operasi dasar PSO diberikan oleh,
Langkah 1: Inisialisasi kawanan dari ruang solusi
Langkah 2: Evaluasi kesesuaian masing-masing partikel
Langkah 3: Ubah gbest, pbest dan velocity
Langkah 4: Pindahkan setiap partikel ke posisi baru
Langkah 5: Goto langkah 2, dan ulangi sampai konvergensi menghentikan kondisi terpenuhi
11.2.4 Perbandingan antara PSO dan GA
Kekuatan GA adalah sifat paralel pencarian mereka. GA menerapkan bentuk pendakian bukit yang kuat yang mempertahankan banyak solusi, menghapus solusi yang tidak menjanjikan, dan memberikan solusi yang masuk akal. Melalui operator genetika, solusi yang lemah bahkan bisa terus menjadi bagian dari solusi kandidat masa depan. Operator genetik yang digunakan sangat penting bagi keberhasilan pencarian. Semua GA memerlukan beberapa bentuk rekombinasi, karena ini memungkinkan terciptanya solusi baru yang dimiliki, berdasarkan keberhasilan orang tua mereka, probabilitas yang lebih tinggi untuk menunjukkan kinerja yang baik.
Sebagian besar teknik evolusioner memiliki prosedur sebagai berikut:
1. Generasi acak dari populasi awal
2. Menghitung nilai kesesuaian untuk setiap subjek. Ini akan langsung tergantung dari jarak ke optimum.
3. Reproduksi penduduk berdasarkan nilai kesesuaian.
4. Jika persyaratan dipenuhi, maka berhentilah. Jika tidak, kembali ke 2.
11.2.5 Aplikasi PSO
PSO telah berhasil diterapkan di banyak bidang: optimasi fungsi, pelatihan jaringan syaraf tiruan, kontrol sistem fuzzy, dan area lain dimana GA dapat diterapkan. Berbagai area aplikasi Particle Swarm Optimization meliputi:
• Operasi dan kontrol Sistem Daya
• Masalah kombinatorial NP-Hard
• Masalah Penjadwalan Pekerjaan
• Masalah Routing Kendaraan
• Jaringan Mobile
• Pemodelan parameter optimal
• Penjadwalan proses batch
• Masalah optimasi multi obyektif
• Pengolahan citra dan masalah pengenalan pola dan sebagainya.

2. Ant Colony Optimization [kembali]

Ant Colony Optimization (ACO) berbasis isapopulasi, bersifat umum untuk mengatasi masalah evolusi atau masalah kultivator, yang biasanya disebabkan oleh jejak gembala yang meletakan perilaku koloni semut yang sesungguhnya. Di ACO, satu set agen perangkat lunak yang disebut semut buatan mencari solusi yang baik untuk masalah optimasi yang diberikan. Untuk menerapkan ACO, masalah optimasi ditransformasikan menjadi masalah untuk menemukan jalur terbaik pada grafik tertimbang.
11.3.1 Inspirasi Biologis
Pada tahun 40an dan 50an abad ke-20, ahli entomologi Prancis Pierre-Paul Grass mengamati bahwa beberapa spesies rayap bereaksi terhadap apa yang dia sebut "rangsangan yang signifikan". Dia mengamati bahwa efek dari reaksi ini dapat bertindak sebagai rangsangan baru yang signifikan bagi serangga yang menghasilkannya dan serangga lainnya di koloni tersebut. Rumput menggunakan istilah stigmergy untuk menggambarkan jenis komunikasi tertentu di mana "pekerja dirangsang oleh kinerja yang telah mereka capai".
Dua karakteristik utama stigmergy yang membedakannya dari bentuk komunikasi lainnya adalah sebagai berikut.
• Stigmergy adalah bentuk komunikasi tidak langsung dan tidak simbolik yang dimediasi oleh lingkungan: serangga bertukar informasi dengan memodifikasi lingkungan mereka;
• Stigmergicinformationis lokal: hanya dapat diakses oleh serangga yang mengunjungi lokus tempat pelepasannya (atau lingkungan terdekatnya).
Stigmergy adalah bentuk komunikasi tidak langsung dan asinkron dimana serangga memanipulasi lingkungan untuk mengangkut informasi ke serangga lainnya, yang kemudian merespons perubahan tersebut.
Unsur-unsur utama dari sistem stigmergik biologis ditunjukkan pada Gambar 11.7:
• Serangga sebagai individu yang bertindak.
• Feromon merupakan pembawa informasi, yang digunakan untuk membuat medan disipasi.
• Lingkungan adalah mekanisme display dan distribusi informasi.
Perhatikan Gambar 11.8 berikut dimana semut bergerak pada garis lurus, yang menghubungkan sumber makanan ke sarang:
Sudah diketahui dengan pasti bahwa sarana utama yang digunakan oleh semut untuk membentuk dan memelihara garis adalah jalur feromon. Semut menyimpan sejumlah feromon sambil berjalan, dan setiap semut secara probabilistik lebih memilih mengikuti arah yang kaya pheromonerather daripada yang lebih buruk. Perilaku dasar semut asli ini dapat digunakan untuk menjelaskan bagaimana mereka dapat menemukan jalan terpendek, yang menghubungkan kembali garis putus-putus setelah munculnya rintangan tak terduga, telah mengganggu jalur awal (Gambar 11.9).
Sebenarnya, begitu rintangan telah muncul, semut-semut itu, yang berada tepat di depan rintangan, tidak dapat terus mengikuti jejak feromon dan oleh karena itu mereka harus memilih antara belok kanan atau kiri. Dalam situasi ini kita bisa mengharapkan setengah semut untuk memilih berbelok ke kanan dan separuh lainnya berbelok ke kiri. Situasi yang sama dapat ditemukan di sisi lain dari hambatan (Gambar 11.10).
Karena proses umpan balik positif ini (autocatalytic), segera semut semua semut akan memilih jalan yang lebih pendek (Gambar 11.11).
11.3.2 Kesamaan dan Perbedaan Antara Semut Nyata dan Semangat Artistik
Ada beberapa perbedaan dan persamaan antara semut asli dan buatan yang dapat dinyatakan sebagai berikut: 11.3.2.1 Kesamaan
• Koloni individu yang bekerja sama - Baik koloni semut asli dan algoritma semut terdiri dari populasi, atau koloni agen individu independen.
• Pheromonetrailandstigmergy-Likerealan, pecandu artifisial saling berbagi tentang lingkungan mereka yang dideritanya.
• Gerakan lokal dan pencarian jalur terpendek-Meskipun semut nyata berjalan melalui negara-negara yang berdekatan dan semut buatan melompat dari satu ke yang lain keadaan berdekatan dari masalah yang dipertimbangkan, baik jalan kaki maupun lompatan memiliki tujuan yang sama, yaitu menemukan saluran yang paling tepat antara titik pusat dan titik temu.
• Kebijakan transisi - Baik semut dan buatan asli akan membangun solusi dengan menerapkan prosedur pengambilan keputusan untuk bergerak melalui negara-negara yang berdekatan.
11.3.2.2 Perbedaan
Perbedaannya sebagai berikut:
• Semut-semut artistik tinggal di dunia yang terpisah. Semua gerakan mereka melompat dari satu keadaan diskrit ke sisi yang lain.
• Semut artistik memiliki ingatan, mereka dapat mengingat keadaan yang telah dikunjungi (daftar tabu dalam model ini).
• Metodologi deposit feromon secara signifikan berbeda antara semut asli dan buatan. Waktu dalam pheromonelaying adalah masalah tergantung dan sering tidak memiliki kesamaan dengan metodologi deposit feromon semut yang sesungguhnya.
• Untuk meningkatkan kinerja secara keseluruhan, algoritma AS dapat diperkaya dengan beberapa kemampuan tambahan yang tidak dapat ditemukan di koloni semut yang sebenarnya.
11.3.3 Karakteristik Ant Colony Optimization
Karakteristik optimasi koloni semut adalah sebagai berikut:
• Algoritma alami karena didasarkan pada perilaku semut nyata dalam membangun jalur dari koloni mereka menjadi sumber makanan dan kembali.
• Paralel dan terdistribusi karena menyangkut populasi agen yang bergerak secara bersamaan, mandiri dan tanpa atasan.
• Koperasi karena masing-masing agen memilih jalur berdasarkan informasi, jalur feromon yang diletakkan oleh agen lainnya, yang sebelumnya telah memilih samepath.
• Serbaguna bahwa hal itu dapat diterapkan pada versi yang sama dari masalah yang sama;
• Kuat bahwa hal itu dapat diterapkan dengan sedikit perubahan pada masalah optimasi kombinatorial lainnya seperti masalah penugasan kuadrat (QAP) dan masalah penjadwalan jobshop (JSP).
11.3.4 Algoritma Optimasi Koloni
Algoritma optimasi koloni semut yang berbeda telah diusulkan. Algoritma optimasi koloni semut asli dikenal sebagai Sistem Ant dan diusulkan pada awal tahun 90an. Sejak itu, sejumlah algoritma ACO lainnya diperkenalkan. Tabel 11.1 memberikan daftar varian Algoritma Optimasi Ant Colony yang berhasil.
Gambar 11.14 memberikan gambaran sempit tentang Algoritma Optimasi Ant Colony.
ACO adalah kelas algoritma, yang anggota pertamanya, yang disebut Ant System, awalnya diusulkan oleh Colorni, Dorigo dan Maniezzo.
11.3.4.1 Sistem Semut
Sistem yang diterapkan pada masalah Sales Man dibicarakan di sini. Ciri utamanya adalah bahwa, pada setiap iterasi, pheromonevalues diperbarui oleh semut m yang telah membangun solusi dalam iterasi itu sendiri.
11.3.4.2 Sistem Koloni Ant
Sumbangan ACS yang paling menarik adalah pengenalan pembaruan pheromone di samping update pheromone yang dilakukan pada akhir proses konstruksi (disebut feromon flut). Feromon lokal dilakukan oleh semua semut setelah setiap tahap konstruksi. Setiap semut menerapkannya hanya pada tepi terakhir yang dilalui:
11.3.4.3 Arus Dasar ACO
Arus operasional dasar dalam Ant Colony Optimization adalah sebagai berikut: Langkah 1: Mewakili ruang solusi dengan grafik konstruksi
Langkah 2: Inisialisasi parameter ACO
Langkah 3: Menghasilkan solusi acak dari setiap perjalanan acak semut
Langkah 4: Update pheromoneintensities
Langkah 5: Goto Langkah 3, dan ulangi sampai convergenceor kondisi berhenti puas.
Algoritma semut generik diberikan seperti ditunjukkan pada Gambar 11.15,
Algoritma Optimalisasi Optimalisasi Teorema Primer seperti ditunjukkan pada Gambar 11.16.
Prosedur langkah demi langkah untuk mengatasi masalah optimasi kombinatorial menggunakan ACO secara singkat adalah:
• Mewakili masalah dalam bentuk kumpulan komponen dan transisi atau dengan cara grafik tertimbang yang dilakukan oleh semut untuk membangun solusi.
• Menentukan dengan tepat arti jalur feromon, yaitu jenis keputusan yang mereka bias. Ini adalah langkah penting dalam implementasi algoritma ACO. Definisi jalur feromon yang baik bukanlah tugas sepele dan biasanya memerlukan pemahaman tentang masalah yang dipecahkan.
• Secara tepat menentukan preferensi heuristik terhadap setiap keputusan yang harus diambil seekor semut saat membangun solusi, yaitu, menentukan informasi heuristik yang terkait dengan setiap transisi komponen. Perhatikan bahwa informasi heuristik sangat penting untuk kinerja yang baik jika algoritma pencarian lokal tidak tersedia atau tidak dapat diterapkan.
• Jika memungkinkan, terapkan algoritma pencarian lokal yang efisien untuk masalah yang sedang dipertimbangkan, karena hasil banyak aplikasi ACO pada masalah optimalisasi kombinatorial NP-load menunjukkan kinerja terbaik dicapai saat menggabungkan ACO dengan pengoptimalan lokal.
• Pilihlah algoritma keamanan dan dapatkan penyelesaian masalah, pertimbangkan aspek-aspek sebelumnya.
• Tune parameter dari algoritma ACO. Titik awal yang baik untuk penentuan parameter adalah dengan menggunakan parameterettings yang ternyata bagus saat menerapkan algoritma ACO pada masalah yang sama atau berbagai masalah lainnya.
Algoritma ACO iteratively melakukan loop yang berisi dua prosedur dasar, yaitu:
• Prosedur yang menentukan bagaimana semut membangun / memodifikasi solusi dari masalah yang harus dipecahkan;
• Prosedur untuk memperbarui pheromonetrails.
11.3.5 Aplikasi Ant Colony Optimization
Ada banyak implementasi meta ACO-heuristik yang diterapkan pada sejumlah masalah optimasi kombinatorial yang berbeda. Aplikasi meliputi:
• Traveling Salesman Problem, di mana seorang salesman harus menemukan rute terpendek yang dengannya ia dapat mengunjungi sejumlah kota, masing-masing kota persis satu kali.
• Masalah Penugasan Kuadrat, masalah penetapan n fasilitas ke n lokasi sehingga biaya penugasan diminimalkan.
• Masalah Penjadwalan Job-Shop, di mana satu set mesin dan satuan kerja tertentu harus diberikan pada interval waktu sedemikian rupa sehingga tidak ada dua pekerjaan yang diproses pada waktu yang sama pada mesin yang sama dan waktu penyelesaian maksimum dari semua operasi diminimalkan
• Masalah Routing Kendaraan, tujuannya adalah untuk menemukan rute kendaraan dengan biaya minimum sehingga:
(a) Setiap pelanggan dikunjungi tepat satu kali dengan satu kendaraan;
(b) Untuk setiap kendaraan, permintaan total tidak melebihi kapasitas kendaraan;
(c) Panjang tur total setiap kendaraan tidak melebihi batas yang ditentukan;
(d) Setiap kendaraan memulai dan mengakhiri turnya pada posisi yang sama.
• Urutan urutan super terpendek yang biasa, jika diberi satu set string di atas alfabet - string dengan panjang minimal yang merupakan urutan super dari setiap string dari rangkaian yang diberikan harus ditemukan (urutan super S dari string A dapat diperoleh dari A dengan memasukkan karakter nol atau lebih dalam A).
• Graph-Coloring Problem, yang merupakan masalah untuk menemukan pewarnaan grafik sehingga jumlah warna yang digunakan minimal.
• Masalah Pengurutan Berurutan, yang terdiri dari menemukan bobot minimum, yang tunduk pada batasan pendahuluan di antara nodus.
• Connection-Oriented Network Routing, dimana semua paket dari sesi yang sama mengikuti jalur yang sama yang dipilih oleh tahap penyiapan awal.
• Connectionless Network Routing dimana paket data dari sesi yang sama dapat mengikuti jalur yang berbeda (Internet-typenetworks).
Tabel11.2 Gambaran umum keseluruhan aplikasi adalah optimalisasi dan peneliti kutu yang dilakukan.

Read More

BAB 7 : Genetic Algorithm Optimazation Problems 

[KEMBALI KE MENU SEBELUMNYA]

DAFTAR ISI

1. Masalah Optimasi Fuzzy

2. Soal Desain Keandalan Multiobjektif

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 [kembali]

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{˜c1x,...,˜ ck 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 [kembali]

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)
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.
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 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 [kembali]

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[kembali]

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[kembali]

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? (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[kembali]

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