| | | | | | | | | | | | | | | | | | | | | | | | | Г | е | н | е | т | и | ч | е | с | к | о | е | | п | р | о | г | р | а | м | м | и | р | о | в | а | н | и | е | | | | | | | | | | | | | | | | | | | | | | | | | |
| 3.1.96 | |
| Для решения многих задач существуют алгоритмы, дающие точное их решение. |
| Однако существуют задачи, сложность которых не позволяет найти точного решения |
| из-за невозможности человека предложить такой алгоритм. Такие сложные задачи |
| кроме оптимального (самого лучшего) решения могут иметь множество других |
| решений, более-менее подходящих или совсем неподходящих. |
| Генетическое программирование основывается на модели эволюции. Алгоритм |
| работает над популяцией индивидуумов, представленных "хромосомными наборами". |
| Каждая такая "хромосома" представляет собой запись решения целевой задачи |
| (обычно в двоичном алфавите, но можно использовать любой алфавит). Кроме |
| популяции необходимо правило естественного отбора - правило определения |
| "хорошести" того или иного решения задачи. На каждом этапе эволюции для каждой |
| особи популяции определяется ее "жизненная сила" - хорошесть представляемого |
| ею решения целевой задачи. |
| Так же как и в природе не обойтись без скрещивания, мутации и вымирания. |
| Скрещивание | представляет собой процесс создания особи (индивида) часть генома |
| (хромосомного набора) которого принадлежит одной особи, часть другой и т.д. | В | |
| отличие от природной эволюции, в скрещивании могут принимать участие более 2 | |
| особей популяции | . | Мутация | представляет собой процесс случайного изменения |
| хромосомного набора у определенного числа особей популяции. | Вымирание | - |
| удаление определенного числа членов популяции пропорционально их возрасту и |
| "жизненной" силы. |
| |
| Псевдоалгоритм выглядит следующим образом: |
| |
| t = 0 |
| создать популяцию; |
| подсчитать жизненную силу(t); |
| while not done do |
| t = t + 1 |
| скрещивание(t); |
| мутация(t); |
| подсчет жизненной силы(t); |
| вымирание(t); |
| end while |
| |
| Алгоритм заканчивает работу когда один или несколько членов популяции |
| достигают определенного заранее заданного уровня "жизненной силы" - т.е. мы |
| получаем решение заранее заданного "качества". |
| |
| Генетический алгоритм очень хорошо решает многокритериальные переборные |
| задачи, задачи линейного программирования и др. Скорость нахождения решения и |
| нахождение глобального оптимума зависит от размера популяции, правила |
| скрещивания, скорости размножения и мутации, зависимости вымирания от возраста |
| и жизненной силы и т.п. |
| |