Saya tidak akan memperkenalkan prinsip -prinsip terperinci dan definisi spesifik algoritma genetika di sini. Jika Anda ingin tahu, Anda dapat menggunakan Baidu untuk mempelajarinya. Di sini saya akan secara singkat memperkenalkan pemahaman Anda tentang algoritma genetika. Artikel ini menggunakan aturan biner untuk pengkodean gen.
Ide Algoritma:
Algoritma genetika mengacu pada teori evolusi Darwin dan percaya bahwa spesies berkembang dalam arah yang positif (kelangsungan hidup yang paling cocok), sehingga dapat dipertimbangkan bahwa setelah aljabar yang cukup, nilai maksimum yang diperoleh sangat dekat dengan nilai maksimum yang sebenarnya.
Langkah Algoritma:
Bagian Implementasi Algoritma
1. Populasi individu (di sini dianggap kromosom), pada individu, kami menambahkan dua atribut untuk individu ini, kebugaran (nilai fungsi) yang sesuai dengan gen dan gen individu.
Kromosom kelas publik {private boolean [] gen; // urutan gen skor ganda pribadi; // skor fungsi yang sesuai} 2. Hasilkan urutan gen secara acak. Apakah setiap posisi gen adalah 0 atau 1, ini adalah cara yang sepenuhnya acak untuk mencapainya.
kromosom publik (ukuran int) {if (size <= 0) {return; } initgenesize (ukuran); untuk (int i = 0; i <size; i ++) {gen [i] = math.random ()> = 0.5; }} private void initGenesize (ukuran int) {if (size <= 0) {return; } gen = boolean baru [ukuran]; } 3. Konversi gen menjadi nilai yang sesuai, misalnya, angka yang sesuai dengan 101 adalah 5, dan operasi bit digunakan di sini untuk mengimplementasikannya.
public int getNum () {if (gen == null) {return 0; } int num = 0; untuk (boolean bool: gen) {num << = 1; if (bool) {num += 1; }} return num; } 4. Jika mutasi gen terjadi, lokasi mutasi sepenuhnya diimplementasikan secara acak. Prinsip mutasi adalah berubah dari 1 ke 0 dan 0 menjadi 1.
mutasi public void (int num) {// Izinkan mutasi int size = gen.length; untuk (int i = 0; i <num; i ++) {// Cari lokasi mutasi int at = ((int) (math.random () * ukuran)) ukuran %; // Nilai setelah mutasi boolean bool =! Gen [at]; gen [at] = bool; }} 5. Gen kloning digunakan untuk menghasilkan generasi berikutnya. Langkah ini adalah menyalin gen yang ada.
klon kromosom statis publik (kromosom akhir c) {if (c == null || c.gene == null) {return null; } Copy kromosom = kromosom baru (); copy.initgenesize (c.gene.length); untuk (int i = 0; i <c.gene.length; i ++) {copy.gene [i] = c.gene [i]; } return copy; } 6. Kedua orang tua menghasilkan generasi berikutnya, dan di sini dua orang menghasilkan dua keturunan individu. Gen spesifik mana yang berbeda dari siswa, sepenuhnya acak.
Daftar statis publik <Cromosome> genetic (kromosom P1, kromosom P2) {if (p1 == null || p2 == null) {// Ada salah satu kromosom yang kosong dan tidak menghasilkan pengembalian generasi berikutnya nol; } if (p1.gene == null || p2.gene == null) {// Ada salah satu kromosom yang tidak memiliki urutan gen dan tidak menghasilkan pengembalian generasi berikutnya nol; } if (p1.gene.length! = p2.gene.length) {// Panjang urutan gen kromosom tidak menghasilkan pengembalian generasi berikutnya nol; } Kromosom C1 = klon (p1); Kromosom C2 = klon (P2); // Buat posisi cross-swap secara acak ukuran int = c1.gene.length; int a = ((int) (math.random () * ukuran)) ukuran %; int b = ((int) (math.random () * ukuran)) % ukuran; int min = a> b? B: A; int max = a> b? A: B; // gen cromex pada posisi untuk (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.gene [i] = c2.gene [i]; c2.gene [i] = t; } Daftar <Cromosome> Daftar = ArrayList baru <Cromosome> (); list.add (C1); list.add (C2); daftar pengembalian; } Algoritma algoritma-genetika algoritma
1. Untuk algoritma genetika, kita perlu memiliki populasi yang sesuai dan beberapa konstanta yang perlu kita tetapkan: jumlah populasi, panjang gen, jumlah mutasi gen, laju mutasi gen, dll. Untuk perincian, silakan merujuk ke kode berikut:
public abstract class GeneticAlgorithm { private List<Chromosome> population = new ArrayList<Chromosome>();//Population private int popSize = 100;//Population number private int geneSize;//Maximum length private int maxIterNum = 500;//Maximum iteration private double mutationRate = 0.01;//Probability of gene mutation private int maxMutationNum = 3;//Maximum mutation asynchronous length Private int Generation = 1; // Berapa generasi yang saat ini diwariskan? BestScore; // Skor Terbaik Private Double WorstScore; // Skor Terburuk Private Totalscore; // Total Skor Private Double Averagescore; // Skor Rata -rata Private Double X; // Catat nilai x terbaik dalam populasi historis swasta ganda y; // Catat nilai y terbaik dalam populasi historis private int gen; // aljabar di mana xy berada} 2. Inisialisasi populasi. Pada awal algoritma genetika, kita perlu menginisialisasi populasi asli, yang merupakan generasi pertama yang asli.
private void init () {for (int i = 0; i <popsize; i ++) {populasi = ArrayList baru <Cromosome> (); Kromosom CHRO = kromosom baru (Genesize); Populasi.Add (CHRO); } cacultescore (); } 3. Setelah populasi awal ada, kita perlu menghitung kebugaran populasi, serta kebugaran terbaik, kebugaran terburuk dan kebugaran rata -rata, dll.
private void cacultescore () {setchromosomescore (populasi.get (0)); BestScore = Population.get (0) .getScore (); worlmscore = populasi.get (0) .getScore (); TotalScore = 0; untuk (chromosome chro: populasi) {setchromosomescore (chro); if (chro.getscore ()> bestscore) {// atur nilai gen terbaik BestScore = chro.getScore (); if (y <BestScore) {x = changex (chro); y = BestScore; genei = generasi; }} if (chro.getScore () <worldscore) {// Tetapkan nilai gen terburuk terburuk = chro.getscore (); } totalscore += chro.getscore (); } averageScore = totalscore / popsize; // Nilai rata -rata yang disebabkan oleh masalah akurasi lebih besar dari nilai terbaik, atur nilai rata -rata ke nilai terbaik averageScore = AverageScore> BestScore? BestScore: Averagescore; } 4. Saat menghitung kebugaran individu, kita perlu menghitung nilai Y yang sesuai berdasarkan gen. Di sini kami menetapkan dua metode abstrak untuk mengimplementasikan implementasi spesifik dengan implementasi kelas.
private void setchromosomescore (chromosome chro) {if (chro == null) {return; } double x = changex (chro); double y = caculate (x); chro.setscore (y); } / ** * @param chro * @return * @description: Konversi biner ke x * / public abstrak double changex (chromosome chro); / ** * @param x * @return * @description: Hitung nilai y berdasarkan x y = f (x) */ public abstrak double caculate (double x); 5. Setelah menghitung kebugaran populasi, kita perlu menggunakan metode perjudian turntable untuk memilih individu yang dapat menghasilkan generasi berikutnya. Ada kondisi di sini bahwa hanya jika kebugaran individu tidak kurang dari kebugaran rata -rata, generasi berikutnya akan dilahirkan (yang paling cocok bertahan).
kromosom pribadi getParentChromosome () {double slice = math.random () * totalscore; Jumlah ganda = 0; untuk (chromosome chro: populasi) {sum += chro.getscore (); // Pergi ke posisi yang sesuai dan kebugaran tidak kurang dari kebugaran rata -rata jika (sum> slice && chro.getscore ()> = averageScore) {return chro; }} return null; } 6. Setelah memilih individu yang dapat menghasilkan generasi berikutnya, Anda harus kawin untuk menghasilkan generasi berikutnya.
private void evolve () {list <romosome> childpopulation = new ArrayList <Cromosome> (); // menghasilkan populasi generasi berikutnya sementara (childpopulation.size () <popsize) {kromosom p1 = getParentchromosome (); Kromosom P2 = getParentchromosome (); Daftar <Cromosome> anak -anak = chromosome.genetic (p1, p2); if (anak -anak! = null) {for (chromosome chro: anak -anak) {childpopulation.add (chro); }}} // Ganti populasi lama dengan daftar populasi baru <Cromosome> t = populasi; populasi = anak -anak; t.clear (); t = null; // mutasi mutasi gen (); // Hitung kebugaran populasi baru Cacultescore (); } 7. Mutasi genetik dapat terjadi selama proses menghasilkan generasi berikutnya.
private void mutation () {for (chromosome chro: populasi) {if (math.random () <mutationrate) {// mutasi gen terjadi int mutationnum = (int) (math.random () * maxMutationNum); chro.mutation (mutationNum); }}} 8. Ulangi langkah -langkah di atas satu per satu.
public void Caculte () {// inisialisasi generasi populasi = 1; init (); while (generasi <maxiternum) {// evolusi genetik populer (); mencetak(); generasi ++; }}Tulis kelas implementasi
Karena kelas algoritma genetika di atas adalah kelas abstrak, kita perlu menulis kelas implementasi untuk kasus tertentu, dengan asumsi kita menghitung nilai maksimum y = 100-log (x) pada [6.106].
1. Kami berasumsi bahwa panjang gen adalah 24 (panjang gen ditentukan oleh panjang efektif dari hasil yang diperlukan), sehingga maksimum biner yang sesuai adalah 1 << 24. Kami membuat pengaturan berikut
Kelas Publik GeneticalGorithMTest memperluas GeneticalGorithm {public static final int num = 1 << 24; GeneticalgorithMtest publik () {super (24); }} 2. Menerapkan metode abstrak nilai x
@Override public double changex (chromosome chro) {// TODO Metode yang dihasilkan secara otomatis Stub return ((1.0 * chro.getnum () / num) * 100) + 6; } 3. Menerapkan metode abstrak y
@Override Public Double Caculyy (double x) {// TODO Metode yang dihasilkan otomatis Stub Return 100 - Math.log (x); }Hasil berjalan
Memikirkan algoritma genetika
Saya telah membaca banyak perkenalan untuk algoritma genetika. Solusi optimal yang disebutkan di atas adalah nilai terbanyak dari generasi terakhir. Saya punya pertanyaan. Mengapa saya tahu bahwa nilai paling banyak di antara semua band di atas, yaitu nilai -nilai XY dalam program, mengapa saya tidak dapat menggunakan nilai XY sebagai nilai hasil akhir dari algoritma genetika?
Kode lengkap
1. Kelas kromosom
/ ***@Deskripsi: kromosom genetik*/ paket com.lulei.genetic.algorithm; impor java.util.arraylist; impor java.util.list; Kromosom kelas publik {private boolean [] gen; // urutan gen skor ganda swasta; // skor fungsi yang sesuai public double getscore () {skor pengembalian; } public void setScore (skor ganda) {this.score = skor; } / *** Ukuran @param* Urutan gen yang dihasilkan secara acak* / kromosom publik (ukuran int) {if (size <= 0) {return; } initgenesize (ukuran); untuk (int i = 0; i <size; i ++) {gen [i] = math.random ()> = 0.5; }} / *** Hasilkan gen baru* / chromosome publik () {} / *** @param c* @return* @description: Gen kloning* / klon kromosom statis publik (kromosom akhir c) {if (c == null || c.gene == null) {return cule; } Copy kromosom = kromosom baru (); copy.initgenesize (c.gene.length); untuk (int i = 0; i <c.gene.length; i ++) {copy.gene [i] = c.gene [i]; } return copy; } / *** @param size* @description: inisialisasi panjang gen* / private void initgeneSize (ukuran int) {if (size <= 0) {return; } gen = boolean baru [ukuran]; } /** * @param c1 * @param c2 * @Description: Genetic generation to produce the next generation*/ public static List<Chromosome> genetic(Chromosome p1, Chromosome p2) { if (p1 == null || p2 == null) { //There is one of the chromosomes that is empty, and does not produce the next generation return null; } if (p1.gene == null || p2.gene == null) {// Ada salah satu kromosom yang tidak memiliki urutan gen, dan tidak menghasilkan pengembalian generasi berikutnya nol; } if (p1.gene.length! = p2.gene.length) {// Panjang urutan gen kromosom tidak menghasilkan pengembalian generasi berikutnya nol; } Kromosom C1 = klon (p1); Kromosom C2 = klon (P2); // Buat posisi cross-swap secara acak ukuran int = c1.gene.length; int a = ((int) (math.random () * ukuran)) ukuran %; int b = ((int) (math.random () * ukuran)) % ukuran; int min = a> b? B: A; int max = a> b? A: B; // gen cromex pada posisi untuk (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.gene [i] = c2.gene [i]; c2.gene [i] = t; } Daftar <Cromosome> Daftar = ArrayList baru <Cromosome> (); list.add (C1); list.add (C2); daftar pengembalian; } /*** @param num* @description: Variasi terjadi pada posisi num gen num* /mutasi public void (int num) {// Izinkan mutasi int size = gen.length; untuk (int i = 0; i <num; i ++) {// Cari posisi mutasi int at = ((int) (math.random () * ukuran)) ukuran %; // Nilai setelah mutasi boolean bool =! Gen [at]; gen [at] = bool; }} / *** @return* @description: Konversi gen menjadi nomor yang sesuai* / int int getNum () {if (gen == null) {return 0; } int num = 0; untuk (boolean bool: gen) {num << = 1; if (bool) {num += 1; }} return num; }} 2. Kelas Genetikgoritma
/ ** *@Deskripsi: */ package com.lulei.genetic.algorithm; impor java.util.arraylist; impor java.util.list; kelas abstrak publik geneticalgorithm {daftar pribadi <Cromosome> populasi = new ArrayList <Cromosome> (); private int popSize = 100;//Popular number private int geneSize;//Maximum gene length private int maxIterNum = 500;//Maximum number of iterations private double mutationRate = 0.01;//Probability of gene mutation private int maxMutationNum = 3;//Maximum variant asynchronous length private int generation = 1;//How many generations are currently inherited to? Private Double BestScore; // Skor Terbaik Private Double WorstScore; // Skor Terburuk Private Totalscore; // Total Skor Private Double Averagescore; // Rata -rata Skor Private Double X; // Catat nilai x terbaik dalam populasi historis swasta ganda y; // Catat nilai y terbaik dalam populasi historis intr private int gen; // aljabar di mana xy terletak publik genetikagoritma (int genesize) {this.genesize = genesize; } public void caculte () {// inisialisasi generasi populasi = 1; init (); while (generasi <maxiternum) {// evolusi genetik populer (); mencetak(); generasi ++; }} / *** @description: hasil output* / private void print () { System.out.println("--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- System.out.println (kebugaran terburuk adalah: " + terburuk); @Description: Population*/ Private Void init () {for (int i = 0; i <Popsize; i ++) {Population = New ArrayList <Chromosome> (); void evolve () {List <Chromosome> Childpopulation = ArrayList baru <Cromosome> (); p2); @Return * @description: Metode roulette memilih kromosom yang dapat mewarisi generasi berikutnya */ privat kromosom getParentchromosome () {double slice = math.random () * totalscore () (slice/ sumscor () (SUMREC; {return chro;}} Null; setchromosomescore (chro); chro.getScore (); (Chromosome chro: populasi) {if (math.random () <mutationrate) {// mutasi gen terjadi int mutationnum = (int) (math.random () * maxMutationNum); setChromosomescore (chromosome chro) {if (chro == null) {return; X * @Return * @Description: Hitung nilai Y berdasarkan pada y = f (x) */ Public Abstrak Ganda Caculate (Double X); Genesize;} public void setmaxiternum (int maxiternum) {this.maxiternum = maxiternum public; BestScore; 3. Kelas GenetikaGoritmtest
/ ** *@Deskripsi: */ package com.lulei.genetic.algorithm; Kelas Publik GeneticalGorithMTest memperluas GeneticalGorithm {public static final int num = 1 << 24; GeneticalgorithMtest publik () {super (24); } @Override public double changex (chromosome chro) {// TODO Metode Stub yang Dihasilkan Otomatis ((1.0 * chro.getnum () / num) * 100) + 6; } @Override public double caculate (double x) {// todo Metode yang dihasilkan otomatis Stub Return 100 - Math.log (x); } public static void main (string [] args) {geneticalgorithmtest test = new geneticalgorithmtest (); test.caculte (); }}Di atas adalah pengantar terperinci untuk algoritma genetika java. Saya harap ini akan membantu semua orang untuk mempelajari algoritma genetik Java.