генетични алгоритми

Генетични алгоритми (GA) - е стохастичен, евристични методи за оптимизация, предложен за първи път от Джон Холанд през 1975. Те се основават на идеята за еволюцията чрез естествен подбор. В допълнение към по-бързо намиране на екстремум, за положителните качества на генетични алгоритми може да се дължи и намирането на "глобален" екстремум. В проблеми, когато целевата функция има значителен брой локални екстремума, за разлика от метода на градиент, генетични алгоритми не са "потънали" в местен най-крайната точка, и ни позволяват да се намери "глобално" минимум.

Генетични алгоритми работят с колекция от физически лица - жители. където всеки индивидуален представлява възможно решение на този проблем. Смята се, мярка за неговата "фитнес", според това как "добра", съответстващо решение на проблема. В природата, това е еквивалентно на оценка на това как ефективно тялото чрез конкуренция за ресурси. Приспособените индивиди имат възможност да "играе" потомството чрез "кръстоска" с други лица в една популация. Това води до появата на нови видове, които съчетават някои от характеристиките, наследени от техните родители. Най-малко приспособени индивиди са по-малко вероятно да бъде в състояние да възпроизвежда потомство, така че тези свойства, които те притежават, постепенно ще изчезнат от населението в процеса на еволюция. Понякога има мутации, или спонтанни промени в гените.

По този начин, от поколение на поколение, добри характеристики се разпространяват сред населението. Хибридизацията на по-силния, води до факта, че наследява най-обещаващите области на пространството на търсене. В крайна сметка на населението ще се доближи до оптимално решение. GA има предимството, че става дума за най-добрите решения в относително кратък период от време.
GA работи следната терминология:

Хромозома - решаването на проблемите на генетична информация носител. Наборът от хромозоми (стойности на параметрите на обективната функция) характеризира индивид. Хромозома състои от гени.
Гените, кодиращи - генетични информационни елементи (параметри на обективната функция). Като ген често изпълнява малко кодиране на информация.
Видове - хромозома избран (параметър комплект за който се иска обективната функция).
Силния - обективна функция стойност за даден набор от параметри по отношение на желаната стойност.

GA произвежда следните действия на частни лица

Генериране на първоначална населението на хромозомите - случайно избрани стойности на параметрите на обективни стойности на функцията за тези параметри е стойността на целевата функция.
Избор - Избор на физически лица от най-добрата адаптивност за репродукцията (чрез сортиране на стойността на целевата функция). Колкото по-добре адаптивността на индивида, по-високи шансовете си на пресичане и ген наследство следващото поколение.
Crossover - кросоувър. Произволно избрани прекъсване точка - частта между съседните битове в един ред. И двете структура родител са разделени на два сегмента от точката. След това, съответните сегменти на различни родители са залепени и получените два генотипове на потомството.
Мутация - случаен вариант на гени. Произволно селектиран ген се променя с определена вероятност на друг.
Инверсия - промяна на реда на частите на кода. Произволно избрани прекъсване точка - частта между съседните битове в един ред. Двете части на основната структура, в разбивка по този въпрос са разменени, а след това залепени заедно.

Първоначално функция HA генерира определен брой възможни решения (образци), и след това се изчислява за всяко устройство - близостта до истината. Тези разтвори произвеждат потомство (произведен операция кросоувър). Повече адаптирани решения имат по-голям шанс да се възпроизвежда, и "слаби" индивиди постепенно "умират". По този начин, в процеса на еволюция. В определени етапи от процеса възникне спонтанно генни промени (мутации и инверсии). Полезни промени, които водят до увеличаване на фитнес индивиди дават тяхното потомство, а "безполезен" промяна "умре." След преминаване, мутации и инверсии фитнес на новото поколение на физическите лица се определя отново. Процесът се повтаря, докато не бъде намерено решение или не достатъчно приближение към него.

Като пример за генетичен алгоритъм, ще обсъдим въпроса за цифрови решения за търсене, обсъждани в тази статия.

Целевата функция ще има формата

Като функция за пресичане ще използва работата на намирането на средното аритметично на двете разглеждани точки. За някои избрани чифтосване точки с най-доброто решение (с стойността на обективната функция най-близо до нула).

Мутация ще бъде работата на генериране на ново случайно число на засегнатото население.

Инверсия стойност ще се промени в хромозома някои малка стойност, извършвайки по този начин търсенето около точката с най-доброто решение.
Изпълнение на C ++

Прилагане на генетични алгоритми не винаги произвеждат най-добри резултати в сравнение с други методи. Въпреки това, този метод има безспорното предимство при решаването на многоизмерните проблеми на търсенето на глобалния екстремум, съдържаща значително количество локален екстремум.