Оператор мутации
призван внести разнообразия в наш островок
цифровой жизни, под его действием у хромосомы изменяется
произвольный ген.
Fitness-функция
: Как и в жизни – не приспособленные виды должны
погибать, «чистить» нашу популяцию будет последняя функция,
называемая функцией приспособления, или Fitness-функцией.
Для каждой хромосомы эта функция возвращает число, обратно
пропорциональное «приспособленности» этой хромосомы, на нее
накладываются условия:
Значение Fitness от идеального решения = 0
Это основное условие, но все же желательно подобрать функцию так,
чтобы ее значение росло, по мере удаления решения от идеального.
Иными словами – чтобы она имела только один минимум.
Теперь можно сформулировать вариант алгоритма
1. Обозначить номер эпохи = 0, создать популяцию хромосом, в генах
которых будет произвольная, не противоречащая задаче, информация
2. Посчитать приспособленность популяции
3. Выбрать из популяции особь А
4. С вероятностью P(скрещивания) выбрать особь B и применить
оператор кроссовера, результирующую особь занести в новую
популяцию.
5. С вероятностью P(мутации) выполнить мутацию произвольной
особи, результирующую особь занести в новую популяцию
6. Выполнить операции 3,4,5 n раз, где n >= размера популяции
7. Создать новую популяцию из лучших особей существующей и
только что сформированной популяции
8. Увеличить номер текущей эпохи
9. Если результат работы удовлетворителен – остановка алгоритма,
иначе – переход к шагу 2.
А.Е. Кононюк Дискретно-непрерывная математика
345
Генетический алгоритм не является строго детерминированным,
например, мы можем сначала выполнить скрещивание всех особей, а
потом мутацию (в рамках данной задачи именно этот подход оказался
более эффективным). Итак, попробуем, на основе описанного, решить
поставленную задачу. Сначала нам понадобится определить
хромосому, которая и будет хранилищем информации о генах.
1.
public
class
Chromosome : IComparable
2.
{
3.
public
double
[] gens;
4.
static
Random
random =
new
Random
();
5.
6.
public
Chromosome()
7.
{
8.
this
.gens =
new
double
[3];
9.
10.
for
(
int
i = 0; i < 3; i++)
11.
{
12.
this
.gens[i] =
random.NextDouble() * 100;
13.
}
14.
this
.fit = fitness(
this
);
15.
}
16.
public
int
CompareTo(
object
obj)
17.
}
* This source code was highlighted with Source Code
Highlighter.
Значение 100 выбрано для примера, это не ограничит общности, даже
если искомая парабола будет иметь кофээфициенты >100
Отметим метод CompareTo, позволяющий нам сортировать списки
объектов Chromosome.
1.
public
class
Population
А.Е. Кононюк Дискретно-непрерывная математика
346
2.
{
3.
Random
random =
new
Random
();
4.
public
List
population;
5.
public
int
count;
6.
public
double
crossProbability;
7.
public
double
MutationProbability;
8.
public
int
age;
9.
10.
public
Population()
11.
{
12.
for
(
int
i = 0; i < 5000; i++)
13.
{
14.
this
.population.Add(
new
Chromosome());
15.
}
16.
}
17.
18.
public
void
GoToNextGeneration()
19.
{
20.
Chromosome chromosome;
21.
for
(
int
i = 0; i < count; i++)
22.
{
23.
chromosome = population[i];
24.
25.
if
(random.NextDouble() <
crossProbability)
26.
{
27.
population.Add(Cross(ch
romosome,population[random.Next(count)]));
28.
}
29.
}
30.
31.
for
(
int
i = 0; i <
population.Count; i++)
32.
{
33.
if
(random.NextDouble() <
MutationProbability)
34.
{
35.
population.Add(Mutate(p
opulation[i]));
Do'stlaringiz bilan baham: |