Langkah-langkah pelaksanaan algoritma genetik dalam PHP

Langkah pelaksanaan algoritma genetik dalam PHP

Pengenalan:
Algoritma genetik ialah algoritma pengoptimuman berdasarkan prinsip evolusi Dengan mensimulasikan proses genetik dan evolusi dalam alam semula jadi, ia boleh mencari penyelesaian optimum dalam ruang penyelesaian masalah carian. Dalam PHP, kita boleh menggunakan algoritma genetik untuk menyelesaikan beberapa masalah pengoptimuman, seperti menyelesaikan pengoptimuman parameter, pembelajaran mesin, masalah penjadualan, dsb. Artikel ini akan memperkenalkan langkah pelaksanaan algoritma genetik dalam PHP dan menyediakan contoh kod yang berkaitan.

1. Memulakan populasi
Dalam algoritma genetik, populasi merujuk kepada satu set penyelesaian untuk dioptimumkan. Pertama, kita perlu menentukan saiz populasi dan cara setiap individu dikodkan. Kaedah pengekodan yang biasa digunakan termasuk binari, integer, titik terapung, dsb. Pilih kaedah pengekodan yang sesuai mengikut ciri masalah. Berikut ialah contoh kod untuk memulakan populasi:

function generateIndividual($chromosome_length) {
    $individual = [];
    for($i = 0; $i < $chromosome_length; $i++){
        $gene = mt_rand(0, 1);
        $individual[] = $gene;
    }
    return $individual;
}

function generatePopulation($population_size, $chromosome_length) {
    $population = [];
    for ($i = 0; $i < $population_size; $i++) {
        $individual = generateIndividual($chromosome_length);
        $population[] = $individual;
    }
    return $population;
}

2. Fungsi kecergasan
Fungsi kecergasan digunakan untuk menilai kecergasan setiap individu dalam populasi, iaitu kualiti penyelesaian. Mengikut ciri-ciri masalah pengoptimuman, fungsi kecergasan boleh direka bentuk supaya individu yang mempunyai kecergasan yang tinggi mempunyai kebarangkalian yang lebih tinggi untuk dipilih dalam pemilihan, silang dan mutasi. Berikut ialah contoh fungsi kecergasan mudah:

function fitnessFunction($individual) {
    $fitness = 0;
    foreach ($individual as $gene) {
        $fitness += $gene;
    }
    return $fitness;
}

3. Operasi pemilihan
Operasi pemilihan merujuk kepada pemilihan beberapa individu daripada populasi sebagai ibu bapa untuk membiak generasi seterusnya. Matlamat operasi pemilihan adalah untuk memilih individu yang mempunyai kecergasan yang tinggi supaya maklumat genetik yang sangat baik dapat disampaikan kepada generasi akan datang. Pemilihan biasanya dibuat menggunakan kaedah seperti pemilihan rolet, pemilihan kejohanan, dsb. Berikut ialah contoh pemilihan rolet mudah:

function selection($population, $fitness_values) {
    $total_fitness = array_sum($fitness_values);
    $probabilities = [];
    foreach ($fitness_values as $fitness) {
        $probabilities[] = $fitness / $total_fitness;
    }
    $selected_individuals = [];
    for ($i = 0; $i < count($population); $i++) {
        $random_number = mt_rand() / mt_getrandmax();
        $probability_sum = 0;
        for ($j = 0; $j < $population_size; $j++) {
            $probability_sum += $probabilities[$j];
            if ($random_number < $probability_sum) {
                $selected_individuals[] = $population[$j];
                break;
            }
        }
    }
    return $selected_individuals;
}

4. Operasi silang
Operasi silang merujuk kepada memilih beberapa individu daripada individu induk untuk pertukaran gen bagi menghasilkan individu generasi seterusnya. Matlamat operasi silang adalah untuk mendapatkan maklumat genetik yang lebih baik dengan menukar gen. Berikut ialah contoh silang dua mata mudah:

function crossover($parent1, $parent2) {
    $chromosome_length = count($parent1);
    $crossover_point1 = mt_rand(1, $chromosome_length - 1);
    $crossover_point2 = mt_rand($crossover_point1, $chromosome_length - 1);
    $child1 = array_merge(array_slice($parent2, 0, $crossover_point1),
                        array_slice($parent1, $crossover_point1,
                        $crossover_point2 - $crossover_point1),
                        array_slice($parent2, $crossover_point2));
    $child2 = array_merge(array_slice($parent1, 0, $crossover_point1),
                        array_slice($parent2, $crossover_point1,
                        $crossover_point2 - $crossover_point1),
                        array_slice($parent1, $crossover_point2));
    return [$child1, $child2];
}

5. Operasi mutasi
Operasi mutasi merujuk kepada mutasi gen individu secara rawak untuk meningkatkan kepelbagaian populasi dan mengelakkan daripada terjerumus ke dalam penyelesaian optimum tempatan. Mutasi biasanya dicapai dengan memilih kedudukan gen secara rawak dan secara rawak mengubah nilainya. Berikut ialah contoh operasi mutasi mudah:

function mutation($individual, $mutation_rate) {
    for ($i = 0; $i < count($individual); $i++) {
        $random_number = mt_rand() / mt_getrandmax();
        if ($random_number < $mutation_rate) {
            $individual[$i] = 1 - $individual[$i];
        }
    }
    return $individual;
}

6. Lelaran algoritma
Empat operasi di atas (pemilihan, silang, mutasi) membentuk operasi asas algoritma genetik. Melalui berbilang lelaran, pemilihan, persilangan dan operasi mutasi dilakukan untuk mengoptimumkan kualiti penyelesaian secara beransur-ansur sehingga syarat penamatan dipenuhi (seperti mencapai bilangan lelaran maksimum atau mencapai penyelesaian optimum). Berikut ialah contoh proses lelaran algoritma genetik:

function geneticAlgorithm($population_size, $chromosome_length, $mutation_rate, $max_generations) {
    $population = generatePopulation($population_size, $chromosome_length);
    $generation = 0;
    while ($generation < $max_generations) {
        $fitness_values = [];
        foreach ($population as $individual) {
            $fitness_values[] = fitnessFunction($individual);
        }
        $selected_individuals = selection($population, $fitness_values);
        $next_population = $selected_individuals;
        while (count($next_population) < $population_size) {
            $parent1 = $selected_individuals[mt_rand(0, count($selected_individuals) - 1)];
            $parent2 = $selected_individuals[mt_rand(0, count($selected_individuals) - 1)];
            list($child1, $child2) = crossover($parent1, $parent2);
            $child1 = mutation($child1, $mutation_rate);
            $child2 = mutation($child2, $mutation_rate);
            $next_population[] = $child1;
            $next_population[] = $child2;
        }
        $population = $next_population;
        $generation++;
    }
    // 取得最佳个体
    $fitness_values = [];
    foreach ($population as $individual) {
        $fitness_values[] = fitnessFunction($individual);
    }
    $best_individual_index = array_search(max($fitness_values), $fitness_values);
    $best_individual = $population[$best_individual_index];
    return $best_individual;
}

Kesimpulan:
Artikel ini memperkenalkan langkah pelaksanaan algoritma genetik dalam PHP dan menyediakan contoh kod yang berkaitan. Dengan memulakan populasi, mereka bentuk fungsi kecergasan, melakukan pemilihan, operasi silang dan mutasi, dan mengoptimumkan kualiti penyelesaian melalui berbilang lelaran, kami boleh menggunakan algoritma genetik untuk menyelesaikan beberapa masalah pengoptimuman. Saya harap artikel ini akan membantu anda memahami dan melaksanakan algoritma genetik dalam PHP.

Atas ialah kandungan terperinci Langkah-langkah pelaksanaan algoritma genetik dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!