Пример использования генетических алгоритмов
В этой заметке вы найдете пример практического применения генетических алгоритмов. Предполагается, что вы уже в курсе, что это такое, или по крайней мере прочитали соответствующую статью в Википедии.
Постановка задачи следующая. Есть множество точек, принадлежащих графику некой функции. Нужно найти полином N-ой степени, проходящий как можно ближе к этим точкам. Другими словами, нужно аппроксимировать функцию. Где-то мы это уже видели, правда?
Сплайны — это, конечно, хорошо, но мир клином на них не сошелся. Представьте, что нам нужно аппроксимировать функцию стандартного нормального распределения, чтобы не хранить в программе заранее рассчитанные координаты четырех сотен точек.
Сплайны в этом случае будут неэффективны. Какая разница, что хранить — координаты всех точек или коэффициенты сотни полиномов 4-ой степени? Можно проигнорировать часть точек, но тогда пострадает точность аппроксимации, а выигрыш в объеме хранимых данных все равно будет невелик.
Генетические алгоритмы позволяют подобрать коэффициенты одного полинома таким образом, чтобы его график проходил максимально близко к графику аппроксимируемой функции. Вот программа на языке Perl, предназначенная для поиска таких полиномов.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | #!/usr/bin/perl # аппроксимация функции с помощью полинома степени MAX_POWER # поиск коэффициентов производится генетическим алгоритмом # (c) Alexandr A Alexeev 2010 | http://eax.me/ use strict; # аппроксимируем функцию полиномом ___ степени use constant MAX_POWER => 4; # сколько особей отбираем в каждом поколении use constant BEST_CNT => 64; # используем каждую ___ точку use constant POINT_USE_FREQ => 1; # загружаем координаты точек аппроксимируемой функции my %f_tbl; my $fname = shift; die "Usage: $0 fname.csv\n" unless($fname); open FID, "<", $fname; my $t; while(<FID>) { if(++$t == POINT_USE_FREQ) { $t = 0; chomp; my($x, $y) = split/\;/; $f_tbl{$x} = $y; } } close FID; # $p[i]->{data} = [a0, a1, a2, ...] # $p[i]->{rslt} = f my @p; # нулевое поколение for(0..BEST_CNT-1) { my @t; push @t, 100 - rand(200) for(0..MAX_POWER); push @p, { data => \@t }; } my $gen = 0; # номер поколения $p[0]->{rslt} = 10; # для входа в цикл # поиск коэффициентов с помощью ГА while($p[0]->{rslt} >= 0.0001) { $gen++; # 1. -------- скрещивание + мутации -------- for my $i (0..BEST_CNT-2) { for my $j($i+1..BEST_CNT-1) { my @t; # скрещивание push @t, ($p[$i]->{data}[$_] + $p[$j]->{data}[$_])/2 for(0..MAX_POWER); # 50% потомства - мутанты if(rand() < 0.5) { $t[$_] += $t[$_]*(4-rand(8)) for(0..MAX_POWER); } push @p, { data => \@t }; } } # for ... # предки вымирают shift @p for(0..BEST_CNT-1); # -------- 2. селекция -------- my $n_items = scalar @p; # вычисляем значения целевой функции $p[$_]->{rslt} = rslt_f($p[$_]->{data}) for(0..$n_items-1); # сортируем особей по значению целевой функции @p = sort { $a->{rslt} <=> $b->{rslt} } @p; # отбираем лучших особей my @next_p; push @next_p, $p[$_] for(0..BEST_CNT-1); @p = @next_p; # выводим номер поколения и значение # целевой функции у "лучшего" потомка print $gen.";".$p[0]->{rslt}.";"; # выводим формулу для OpenOffice my $i = 0; for(@{$p[0]->{data}}) { my $str = sprintf "%.05f", $_; $str =~ s/\./\,/; my $sign = $str =~ /^-/ ? "" : "+"; if($i > 0) { print $sign; $str .= $i == 1 ? "*A2" : "*POWER(A2;$i)"; } $i++; print $str; } print "\n"; } # функция приспособленности sub rslt_f { my ($aref) = @_; my $max_delta = 0; for my $x(keys %f_tbl) { my $delta = abs($f_tbl{$x} - calc_f($aref, $x)); $max_delta = $delta > $max_delta ? $delta : $max_delta; } return $max_delta; } # вычисление функции-аппроксимации # в точке x при заданных коэффициентах sub calc_f { my ($aref, $x) = @_; my $rslt; for(0..MAX_POWER) { $rslt += $aref->[$_]*($x ** $_); } return $rslt; } |
В качестве аргумента скрипт принимает имя файла, состоящего из строк с координатами точек:
0.01;0.5040
0.02;0.5080
0.03;0.5120
0.04;0.5160
0.05;0.5199
0.06;0.5239
0.07;0.5279
0.08;0.5319
0.09;0.5359
0.10;0.5398
0.11;0.5438
0.12;0.5478
...
Роль ДНК в генетическом алгоритме играет массив из MAX_POWER+1 чисел — это коэффициенты полинома. Приспособленность особи определяется, как максимальное отклонение графика полинома от графика аппроксимируемой функции. Чем меньше отклонение, тем более приспособленной считается особь. В скрещивании принимают участие BEST_CNT наиболее приспособленных особей. При скрещивании коэффициенты потомка вычисляются, как среднее арифметическое коэффициентов родителей. 50% потомства мутирует — к каждому коэффициенту прибавляется случайное число, лежащее где-то в диапазоне от -4 до +4 умножить на коэффициент.
На подбор алгоритма у меня ушло несколько часов. Думаю, у людей, более часто работающих с ГА на такие вещи уходит от силы минут 15. С помощью приведенного скрипта мне удалось найти полином, аппроксимирующий функцию стандартного нормального распределения на отрезке [0;4] с погрешностью не более 0,0048:
Φ(x) ~ 0.4953 + 0.461 · x — 0.12472 · x2 + 0.00499 · x3 + 0.001335 · x4
при этом:
Φ(x) = 1 — Φ(-x)
Φμ,σ(x) = Φ((x — μ) / σ)
Последняя формула — для нормального распределения с мат ожиданием μ и дисперсией σ2.
Только подумайте — никаких таблиц, никаких экспонент и интегралов! Все, что нам нужно — это 5 чисел, 4 операции сложения и 7 операций умножения. Всего одна строчка кода на любом процедурном языке программирования. Погрешность менее одной сотой!
Хотите другую функцию? Пожалуйста — вот вам синус на интервале [0; pi/2] с погрешностью 0.00013:
sin(x) ~ 0.00014 + 0.99614 · x + 0.01973 · x2 — 0.20319 · x3 + 0.02855 · x4
Чтобы добиться такой же точности с помощью ряда Тейлора, нужно использовать многочлен 5-ой степени. Тем не менее, для синусов, косинусов, экспонент и логарифмов, наверное, ряды все-таки лучше подходят — и формулы короче и погрешность не такая уж большая.