Optimization Problem Solved by a Genetic Algorithm - Wifi Antenna

Optimization Problem Solved by a Genetic Algorithm - Wifi Antenna

Misalkan Anda menjalankan bisnis kecil di kota Anda, sebut saja kota Anda kota Padang. Dimana klinik lokal menjadi rumah sakit, membangun sebuah sekolah dasar 15 mil di barat laut perpustakaan, grand opening hotel bintang 4 dijadwalkan dalam sebulan dan akhirnya kunci untuk 50 rumah tinggal lainnya diharapkan menjadi diserahkan kepada pemiliknya pada akhir tahun. Jika bisnis Anda adalah menyediakan Internet untuk penduduk setempat, Anda tidak punya pilihan selain memperluas layanan Anda untuk beradaptasi dengan meningkatnya permintaan.

Pada hari Senin pagi Anda duduk di belakang desktop kantor Anda, beberapa pencarian Google dan beberapa email kemudian Anda memesan antena kelas baru yang dapat memberikan data 10 kali lebih banyak daripada instalasi Anda saat ini. Sepuluh hari kerja kemudian, X3100 Anda yang baru tiba dan beberapa surat kabar bekerja kemudian, Tuan Joe si pengirim barang akan kembali ke Jakarta. Sama seperti dia naik ke kursi pengemudi, Anda bergegas ke kendaraannya untuk bertanya: Maaf, Tuan, tetapi Anda lupa memberi saya manual yang menunjukkan di mana antena kelas A ini harus dipasang? Tuan Joe menjawab Anda dengan sopan: "Saya hanya mengirimkan barang-barang yang saya sayangi dan perusahaan kami hanya memasok produk, sisanya jika ada pada Anda". Anda perlu menyelesaikannya!

Ini merupakan soal yang diberi narasi sederhana agar lebih menarik dengan masalah teknik dan mudah-mudahan pada akhir posting ini, kami akan menyelesaikannya. Sekarang mari kita lihat potongan-potongan puzzle ini. Mari kita anggap bahwa X3100 baru saya adalah menyediakan Internet kecepatan tinggi ke 5 lokasi berbeda. Setiap lokasi ditentukan oleh dua properties;

1. Koordinat (x, y) (dalam kilometer)
2. Jam penggunaan rata-rata per bulan (dalam jam)

Sekarang Anda kembali ke kantor Anda, duduk di kursi hangat Anda kali ini menggaruk-garuk kepala Anda di sana-sini ketika hal itu mengenai Anda: Saya dapat menyelesaikan ini, saya selalu memberikan kualitas terbaik kepada pelanggan saya dan tidak pernah dalam 7 tahun bisnis memiliki satu keluhan utama. Saya dikenal memberikan kecepatan maksimum di mana Internet paling dibutuhkan. Itu selalu menjadi tujuan utama Anda dan Anda hanya ingin melanjutkan dengan cara ini.

Jika saya katakan kepada Anda bahwa sekarang, kami telah menyelesaikan 50% dari masalah kami, Anda mungkin ingin tahu lebih banyak. Masalah yang kita hadapi di sini - penentuan lokasi yang tepat untuk menginstal X3100 adalah masalah optimisasi rekayasa yang dapat dirumuskan sebagai berikut:

• Objective Function: memaksimalkan kecepatan Internet di mana konsumsi adalah yang tertinggi. Ini sama dengan: meminimalkan jumlah jarak yang ditimbang oleh jam penggunaan rata-rata. Kita dapat menerima konsep ini dengan mengakui bahwa ada korelasi langsung antara antena-konsumen jarak dan kecepatan (semakin tinggi jarak, semakin lambat kecepatannya). Karena prioritas diberikan kepada klien dengan konsumsi yang lebih tinggi, protokol ini harus dimasukkan dalam fungsi tujuan. Maafkan keterampilan menggambar saya di bawah ini, saya perlu meningkatkan keterampilan saya dalam perangkat lunak menggambar komputer (menunggu saran Anda di bagian komentar), dari itu kita dapat menulis fungsi tujuan (atau fungsi kebugaran) untuk masalah kita.

• Constraints: kota ini memiliki banyak ruang kosong tetapi Anda kotamadya memiliki peraturan baru. Anda hanya diizinkan mengatur antena di zona Z1, yang kebetulan merupakan hutan yang tidak dapat dihuni di utara perpustakaan umum. Diberikan sistem koordinat referensi, kami terbatas pada area Z1 berikut dengan:

Masalah minimisasi yang terkendala secara umum dapat dinyatakan sebagai berikut:

di mana X adalah vektor n-dimensi yang disebut vektor desain (dalam kasus kami vektor desain terdiri dari koordinat x dan y relatif terhadap lokasi antena pada peta), f (X) disebut fungsi tujuan (dalam contoh ini fungsi obyektif adalah jumlah jarak antara antena dan konsumen yang ditimbang oleh konsumsi rata-rata setiap pelanggan), g (X) dan h (X) masing-masing dikenal sebagai kendala ketidaksetaraan dan kesetaraan.

Sekarang bagaimana kita mengatasi masalah optimisasi terbatas ini? Saya tidak ingin meninjau semua teknik optimasi dalam posting ini, itu bukan maksud saya, mungkin saya akan terinspirasi beberapa hari untuk memposting sesuatu, tetapi untuk sesingkat mungkin, ada dua kategori:

1. Teknik traditional mathematical programming. Sebagian besar didasarkan pada evaluasi fungsi tujuan dan turunannya. Mereka sebagian besar pendekatan berbasis gradien.
2. Teknik modern or untraditional methods. Teknik/ cara ini didasarkan pada perilaku biologis, molekul, segerombolan serangga, sistem saraf dll. Mereka adalah metode meta-heuristik.

Sebagian besar teknik modern hanya dikembangkan dalam beberapa tahun terakhir dan kami mulai memperhatikan bahwa mereka muncul sebagai metode yang sangat populer untuk solusi masalah teknik yang kompleks. Keuntungan utama adalah bahwa mereka hanya memerlukan nilai fungsi dan bukan turunannya (yang bisa sulit dan membutuhkan waktu komputasi yang tinggi untuk menghitung). Di antara semua metode modern, algoritma genetika bisa dibilang yang paling terkenal. Algoritma genetika didasarkan pada prinsip-prinsip genetika alami dan seleksi alam.

Meskipun algoritma genetika pertama kali diterapkan oleh Belanda, secara filosofis, mereka didasarkan pada konsep evolusi biologis atau teori Darwin tentang survival of the fittest. Algoritma genetika didasarkan pada prinsip-prinsip genetika alami dan seleksi alam. Elemen dasar genetika alami adalah :

• Reproduksi
• Crossover
• Mutasi

Sedangkan untuk prosesnya, tidak sulit untuk dipahami dan saya akan menjelaskan dalam beberapa baris:

1. Initialization: Populasi titik dibentuk untuk prosedur (tidak seperti metode tradisional di mana kami memilih titik awal). Populasi ini dapat diinisiasi secara acak atau dapat menghormati beberapa kendala kami
2. Evluation: Fungsi kesesuaian setiap kromosom (setiap vektor) populasi dievaluasi.
3. Sorting : Populasi diurutkan sesuai dari yang terlemah ke kebugaran terkuat (tergantung apakah itu adalah minimalisasi masalah maksimalisasi). Dalam kasus kami dari yang terlemah ke yang terkuat sejak f (X) diminimalkan.
4. Selection: Kromosom yang memperoleh kebugaran terendah dipilih sebagai Elit. Dari populasi yang tersisa, anak-anak dibentuk oleh crossover (perkawinan dua kromosom) atau oleh mutasi genetik (secara acak mengubah gen kromosom). Generasi lama digantikan dengan populasi baru untuk membentuk generasi berikutnya.

Proses 2 hingga 4 diulangi sampai kriteria berhenti terpenuhi (biasanya kita mencapai jumlah generasi maksimum atau toleransi konvergensi tertentu dihormati). 

Proses evolusi ini sangat mudah diprogram. Sebenarnya kode utama yang saya gunakan untuk menyelesaikan masalah antena X3100 kami adalah kode 76 baris Matlab. Berikut koding programnya, klik disini.

Selanjutnya menjalankan program, dimana penduduk kota terdata 500, dimana 10 elit, 130 bermutasi dan sisanya (360) adalah dengan crossover. kami mendapatkan koordinat berikut untuk mengatur antena X3100 kami yang indah sekaligus menghormati peraturan kota menurut Z1:

X = 6.25 

Y = 6.39

Sekarang, mari kita asumsikan balai kota mengeluarkan hukum baru yang membentang Z1 untuk membentuk domain yang lebih besar Z2 yang didefinisikan oleh:

Memodifikasi batas atas dan bawah, mengklik jalankan dan beberapa detik kemudian kami memiliki lokasi yang tepat dari antena X3100. 

(X = 5.868 dan Y = 2.577).