Если возникли вопросы

При возникновении вопросов по использованию набора компонент, реализующих генетическия алгоритм, Вы можете решить проблему следующим образом:

1.	Задайте Ваш вопрос на форуме http://forum.basegroup.ru. Форум посвящен вопросам анализа, в частности практическому применению нейронных сетей.

2.	Ищите дополнительную информацию на сайте http://www.basegroup.ru. Информация на сайте часто обновляется, и вполне возможно, что в опубликованных материалах Вы найдете ответ на свой вопрос.

3.	Если возник вопрос по интерпретации какого либо термина для его решения Вы можете посетить глоссарий http://glossary.basegroup.ru

4.	Сообщите о Ваших проблемах по электронной почте по адресу gene@basegroup.ru. По возможности, в письме опишите проблему как можно подробнее.

This help file was created with HelpScribble.


Введение

Генетические алгоритмы предназначены для решения задач оптимизации. Примером подобной задачи может служить обучение нейросети, то есть подбора таких значений весов, при которых достигается минимальная ошибка. При этом в основе генетического алгоритма лежит метод случайного поиска. Основным недостатком случайного поиска является то, что нам неизвестно сколько понадобится времени для решения задачи. Для того, чтобы избежать таких расходов времени при решении задачи, применяются методы, проявившиеся в биологии. При этом используются методы открытые при изучении эволюции и происхождения видов. Как известно, в процессе эволюции выживают наиболее приспособленные особи. Это приводит к тому, что приспособленность популяции возрастает, позволяя ей лучше выживать в изменяющихся условиях.

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов.

This help file was created with HelpScribble.


Представление объектов

Из биологии мы знаем, что любой организм может быть представлен своим фенотипом, который фактически определяет, чем является объект в реальном мире, и генотипом, который содержит всю информацию об объекте на уровне хромосомного набора. При этом каждый ген, то есть элемент информации генотипа, имеет свое отражение в фенотипе. Таким образом, для решения задач нам необходимо представить каждый признак объекта в форме, подходящей для использования в генетическом алгоритме. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без информации о внутренней структуре объекта, что и обуславливает его широкое применение в самых разных задачах.

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

This help file was created with HelpScribble.


Кодирование признаков, представленных целыми числами

Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Для того, чтобы избежать эту проблему лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма. Значения кодов Грея рассмотрены в таблице ниже:

Двоичное кодирование	Кодирование по коду Грея

0	0000	0h	0	0000	0h

1	0001	1h	1	0001	1h

2	0010	2h	3	0011	3h

3	0011	3h	2	0010	2h

4	0100	4h	6	0110	6h

5	0101	5h	7	0111	7h

6	0110	6h	5	0101	5h

7	0111	7h	4	0100	4h

8	1000	8h	12	1100	Ch

9	1001	9h	13	1101	Dh

10	1010	Ah	15	1111	Fh

11	1011	Bh	14	1110	Eh

12	1100	Ch	10	1010	Ah

13	1101	Dh	11	1011	Bh

14	1110	Eh	9	1001	9h

15	1111	Fh	8	1000	8h

Таблица 1. Соответствие десятичных кодов и кодов Грея.

Таким образом, при кодировании целочисленного признака мы разбиваем его на тетрады и каждую тетраду преобразуем по коду Грея.

В практических реализациях генетических алгоритмов обычно не возникает необходимости преобразовывать значения признака в значение гена. На практике имеет место обратная задача, когда по значению гена необходимо определить значение соответствующего ему признака.

Таким образом, задача декодирования значения генов, которым соответствуют целочисленные признаки, тривиальна.

This help file was created with HelpScribble.


Кодирование признаков, которым соответствуют числа с плавающей точкой

Самый простой способ кодирования, который лежит на поверхности – использовать битовое представление. Хотя такой вариант имеет те же недостатки, что и для целых чисел. Поэтому на практике обычно применяют следующую последовательность действий:

Разбивают весь интервал допустимых значений признака на участки с требуемой точностью.

Принимают значение гена как целочисленное число, определяющее номер интервала (используя код Грея).

В качестве значения параметра принимают число, являющиеся серединой этого интервала.

Рассмотрим вышеописанную последовательность действий на примере:

Допустим, что значения признака лежат в интервале [0,1]. При кодировании использовалось разбиение участка на 256 интервалов. Для кодирования их номера нам потребуется таким образом 8 бит. Допустим значение гена: 00100101bG (заглавная буква G показывает, что используется кодирование по коду Грея). Для начала, используя код Грея, найдем соответствующий ему номер интервала: 25hG->36h->54d. Теперь посмотрим, какой интервал ему соответствует… После несложных подсчетов получаем интервал [0,20703125, 0,2109375]. Значит значение нашего параметра будет (0,20703125+0,2109375)/2=0,208984375.

This help file was created with HelpScribble.


Определение фенотипа объекта по его генотипу

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит

00101010100101001101

Теперь мы можем определить значения признаков:

Признак	Значение 	Двоичное	Десятичное

 	гена	значение	значение

Признак 1	0010	0011	3

Признак 2	1010	1100	12

Признак 3	1001	1110	14

Признак 4	0100	0111	7

Признак 5	1101	1001	9

This help file was created with HelpScribble.


Основные генетические операторы

Как известно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание (его также называют кроссовер или кроссинговер). Этот оператор определяет передачу признаков родителей потомкам. Действует он следующим образом:

из популяции выбираются две особи, которые будут родителями;

определяется (обычно случайным образом) точка разрыва;

потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора:

Хромосома_1:	0000000000

Хромосома_2:	1111111111

Допустим разрыв происходит после 3-го бита хромосомы, тогда

Хромосома_1:	0000000000 >>	0001111111	Результирующая_хромосома_1

Хромосома_2:	1111111111 >> 1110000000	Результирующая_хромосома_2

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

Следующий генетический оператор предназначен для того, чтобы поддерживать разнообразие особей с популяции. Он называется оператором мутации. При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется.

Кроме того, используется еще и так называемый оператор инверсии, который заключается в том, что хромосома делится на две части, и затем они меняются местами. Схематически это можно представить следующим образом:

0001111111 >>	111111000

В принципе для функционирования генетического алгоритма достаточно этих трех генетических операторов, но на практике применяют еще и некоторые дополнительные операторы или модификации этих трех операторов. Например, кроссовер может быть не одноточечный (как было описано выше), а многоточечный, когда формируется несколько точек разрыва (чаще всего две). Кроме того, в некоторых реализациях алгоритма оператор мутации представляет собой инверсию только одного случайно выбранного бита хромосомы.

This help file was created with HelpScribble.


Схема функционирования генетического алгоритма

Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.

1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B0 = {A1,A2,…,Ak)

2. Вычислить приспособленность каждой особи FAi = fit(Ai) , i=1…k и популяции в целом Ft = fit(Bt) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.

3. Выбрать особь Ac из популяции. Ac = Get(Bt)

4. С определенной вероятностью (вероятностью кроссовера Pc) выбрать вторую особь из популяции Аc1 = Get(Bt) и произвести оператор кроссовера Ac = Crossing(Ac,Ac1).

5. С определенной вероятностью (вероятностью мутации Pm) выполнить оператор мутации. Ac = mutation(Ac).

6. С определенной вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ac = inversion(Ac).

7. Поместить полученную хромосому в новую популяцию insert(Bt+1,Ac).

8. Выполнить операции, начиная с пункта 3, k раз.

9. Увеличить номер текущей эпохи t=t+1.

10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Теперь рассмотрим подробнее отдельные этапы алгоритма.

Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом на шагах 3 и 4. При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой. При использовании такого метода вероятность выбора хромосомы определяется ее приспособленностью, то есть PGet(Ai) ~ Fit(Ai)/Fit(Bt). Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

Другой важный момент

This help file was created with HelpScribble.


genetic unit

Этот модуль содержит компоненты, реализующие один из вариантов генетического алгоритма.

Components

TChromosome

TGeneticAlgorithm

Types

TGeneDegree

TGetSutability

TOptimizeMethod

This help file was created with HelpScribble.


TChromosome component

Properties	Methods	Tasks

Unit

genetic

Description

Данный класс реализует хромосому, являющуюся основой генетического алгоритма. Фактически она представляет собой строку, полученную конкатенацией генов, описывающих свойства объекта реального мира, и именно над ней производятся все генетические операции.

This help file was created with HelpScribble.


TChromosome - Properties
Properties

 Run-time only	 Key properties

GeneAsFloat

GeneAsInteger

GeneCount

GeneSize

GeneValue

This help file was created with HelpScribble.


TChromosome - Methods
Methods

 Key methods

Create

Destroy

This help file was created with HelpScribble.


About the TChromosome component

TChromosome reference

Purpose

Данный компонент представляет собой объект, реализующий хромосому в виде конкатенации генов, что необходимо для функционирования генетического алгоритма

Tasks

Данный компонент предоставляет программисту простой доступ к генам, которые являются элементами генотипа объекта.

This help file was created with HelpScribble.


GeneAsFloat property

See also

Applies to

TChromosome component

Declaration

property GeneAsFloat[Index: integer: double;

Description

Данное свойство позволяет получить значение, закодированное в гене как число с плавающей точкой. Это число будет находиться в диапазоне [0,1]. Точность, с которой будет определено это число зависит от разрядности генов в хромосоме.

Run-time only

This help file was created with HelpScribble.


GeneAsFloat property - See also
See also

GeneAsInteger

This help file was created with HelpScribble.


GeneAsInteger property

See also

Applies to

TChromosome component

Declaration

property GeneAsInteger[Index: integer: LongInt;

Description

Данное свойство позволяет получить значение, закодированное в гене как целое число. Это число будет находиться в диапазоне, который зависит от используемой разрядности гена. Эти интервалы следующие:

•	8 бит - [0,255]

•	16 бит - [0,65535]

•	32 бита - [0,4294967295]

Run-time only

This help file was created with HelpScribble.


GeneAsInteger property - See also
See also

GeneAsFloat

This help file was created with HelpScribble.


GeneCount property

Applies to

TChromosome component

Declaration

property GeneCount: integer;

Description

Значение данного свойства определяет количество генов в хромосоме, то есть фактически размерность решаемой задачи.

Run-time only

This help file was created with HelpScribble.


GeneSize property

Applies to

TChromosome component

Declaration

property GeneSize: Integer;

Description

Значение данного свойства определяет длинну генов в хромосоме. Возможны значения 8,16 и 32 бита. Не рекомендуется модифицировать это свойство напрямую, так как все соответствующие настройки выполняет компонент TGeneticAlgorithm

Run-time only

This help file was created with HelpScribble.


GeneValue property

Applies to

TChromosome component

Declaration

property GeneValue[Index: integer]: Longword;

Description

Значение этого свойства определяет значение соответсвующего гена в хромосоме. При этом используется внутреннее представление гена. Не рекомендуется использовать это свойство напрямую. Лучше использовать свойства GeneAsFloat или GeneAsInteger

default;

Run-time only

This help file was created with HelpScribble.


Create method

Applies to

TChromosome component

Declaration

constructor Create;

Description

Конструктор класса.

This help file was created with HelpScribble.


TGeneticAlgorithm component

See also	Properties	Methods	Tasks

Unit

genetic

Description

Данный компонент реализует генетический алгоритм. Он позволяет решить широкий класс задач непараметрической многомерной оптимизации.

This help file was created with HelpScribble.


TGeneticAlgorithm component - See also
See also

Схема функционирования генетического алгоритма

This help file was created with HelpScribble.


TGeneticAlgorithm - Properties
Properties

 Run-time only	 Key properties

BestChromosome

Chromosome

ChromosomeCount

Crossover_P

Epoch

GeneCount

GeneDegree

GeneSize

Inversion_P

Mutation_P

OnGetSutability

OptimizeMethod

Suitability

UseElita

This help file was created with HelpScribble.


TGeneticAlgorithm - Methods
Methods

 Key methods

Create

Destroy

Init

OneEpoch

This help file was created with HelpScribble.


About the TGeneticAlgorithm component

TGeneticAlgorithm reference

Purpose

Данный компонент реализует полную функциональность генетического алгоритма.

Tasks

Для использования компонента в приложении достаточно установить его параметры и описать функцию, рассчитывающую приспособленность особей.

This help file was created with HelpScribble.


BestChromosome property

See also

Applies to

TGeneticAlgorithm component

Declaration

property BestChromosome: TChromosome;

Description

Значение данного свойства определяет наиболее приспособленную особь из выборки

Run-time only

Read-only

This help file was created with HelpScribble.


BestChromosome property - See also
See also

OnGetSutability

This help file was created with HelpScribble.


Chromosome property

Applies to

TGeneticAlgorithm component

Declaration

property Chromosome[Index: integer]: TChromosome;

Description

Данное свойство определяет особей, входящих в популяцию, содержащуюся в генетическом алгоритме на текущей эпохе.

Run-time only

Read-only

This help file was created with HelpScribble.


ChromosomeCount property

Applies to

TGeneticAlgorithm component

Declaration

property ChromosomeCount: integer;

Description

Количество особей в популяции

This help file was created with HelpScribble.


Crossover_P property

See also

Applies to

TGeneticAlgorithm component

Declaration

property Crossover_P: double;

Description

Значение этого свойства определяет вероятность применения операции кроссовера (кроссинговера, скрещивания) для выбранных из популяции особей.

This help file was created with HelpScribble.


Crossover_P property - See also
See also

Mutation_P

Inversion_P

This help file was created with HelpScribble.


Epoch property

Applies to

TGeneticAlgorithm component

Declaration

property Epoch: integer;

Description

Значение свойства содержит номер текущей эпохи работы генетического алгоритма и может быть применено для остановки алгоритма после выполнения определнного числа эпох.

Run-time only

This help file was created with HelpScribble.


GeneCount property

Applies to

TGeneticAlgorithm component

Declaration

property GeneCount: integer;

Description

количество генов в особи

This help file was created with HelpScribble.


GeneDegree property

See also

Applies to

TGeneticAlgorithm component

Declaration

property GeneDegree: TGeneDegree;

Description

Данное свойство определяет размерность генов в хромосоме.

This help file was created with HelpScribble.


GeneDegree property - See also
See also

TChromosome.GeneSize

This help file was created with HelpScribble.


GeneSize property

Applies to

TGeneticAlgorithm component

Declaration

property GeneSize: integer;

Description

Значение этого свойства определяет размерность генов в хромосомах. Данное значение не рекомендуется использовать напрямую. Рекомендуется использовать свойство GeneDegree.

Run-time only

This help file was created with HelpScribble.


Inversion_P property

See also

Applies to

TGeneticAlgorithm component

Declaration

property Inversion_P: double;

Description

Значение этого свойства определяет вероятность применения операции инверсии для выбранных из популяции особей.

This help file was created with HelpScribble.


Inversion_P property - See also
See also

Crossover_P

Mutation_P

This help file was created with HelpScribble.


Mutation_P property

See also

Applies to

TGeneticAlgorithm component

Declaration

property Mutation_P: double;

Description

Значение этого свойства определяет вероятность применения операции мутации для выбранных из популяции особей.

This help file was created with HelpScribble.


Mutation_P property - See also
See also

Crossover_P

Inversion_P

This help file was created with HelpScribble.


OnGetSutability property

Applies to

TGeneticAlgorithm component

Declaration

property OnGetSutability: TGetSutability;

Description

This help file was created with HelpScribble.


OptimizeMethod property

Applies to

TGeneticAlgorithm component

Declaration

property OptimizeMethod: TOptimizeMethod;

Description

Значение данного свойства определяет, что будет делать генетический алгоритм - подбирать параметры для минимизации или максимизации значений целевой функции.

This help file was created with HelpScribble.


Suitability property

Applies to

TGeneticAlgorithm component

Declaration

property Suitability: double;

Description

Значение этого свойства показывает приспособленность всей популяции.

Run-time only

Read-only

This help file was created with HelpScribble.


UseElita property

Applies to

TGeneticAlgorithm component

Declaration

property UseElita: boolean;

Description

Если это свойство установлено в True, то при работе генетического алгоритма будет использована стратегия элитизма.

This help file was created with HelpScribble.


Init method

Applies to

TGeneticAlgorithm component

Declaration

procedure Init;

Description

Вызов этого метода приводит к начальной инициализации особей, используемых в генетическом алгоритме случайными значениями.

This help file was created with HelpScribble.


OneEpoch method

Applies to

TGeneticAlgorithm component

Declaration

procedure OneEpoch;

Description

Вызов данного метода приводит к выполнению одного шага генетического алгоритма. При этом производится вычисление приспособленности всех особей из популяции, а на основании этих данных формируется новая популяция.

This help file was created with HelpScribble.


TGeneDegree type

Unit

genetic

Declaration

type TGeneDegree = (Short_8, Midle_16, Long_32);

Description

Этот тип описывает размерность генов в хромосоме. От длинны гена например зависит допустимый интервал значений гена в хромосоме.

This help file was created with HelpScribble.


TGetSutability type

Unit

genetic

Declaration

type TGetSutability = function(Chromosome: TChromosome): double of object;

Description

Функция предназначена для вычисления приспособленности каждой особи в популяции. В нее передается особь, возвращаемое значение - приспособленность особи к решению данной задачи.

This help file was created with HelpScribble.


TOptimizeMethod type

Unit

genetic

Declaration

type TOptimizeMethod = (omMinimize, omMaximize);

Description

Определяет используемый метод оптимизации - минимизировать или максимизировать приспособленность особей в популяции.

This help file was created with HelpScribble.


HelpScribble

HelpScribble is a help authoring tool written by Jan Goyvaerts and available for download at http://www.jgsoft.com/. This help file was created with the unregistered version of HelpScribble, which is why you can read this ad. Once the author of this help file is so honest to register the shareware he uses, you will not see this ad again in his help files.

Recompiling the help project with the registered version is all it takes to get rid of this ad and the little footers below each topic.

HelpScribble is a stand-alone help authoring tool. It does not require an expensive word processor. (Only a help compiler as Microsoft likes keeping the .hlp format secret. Not my fault.)

Here are some of HelpScribble's features:

•	The Setup program will properly install and uninstall HelpScribble and all of its components, including registry keys.

•	Create, edit and navigate through topics right in the main window. No need to mess with heaps of dialog boxes.

•	All topics are listed in a grid in the main window so you won't lose track in big help projects. You can even set bookmarks.

•	Use the built-in Browse Sequence Editor to easily create browse sequences.

•	Use the built-in Window Editor to change the look of your help window and create secondary windows.

•	Use the built-in Contents Editor to create Windows 95-style contents files. Works a lot better than Microsoft's HCW.

•	No need to mess with Microsoft's SHED: use the built-in SHG Editor to create hotspot bitmaps. Draw your hotspots on the bitmap and pick the topic to link to from the list.

•	With the built-in Macro Editor you can easily compose WinHelp macros whenever needed. It will tell you what the correct parameters are and provide information on them.

•	If you have a problem, just consult the online help. The help file was completely created with HelpScribble, of course.

•	HelpScribble is shareware. However, the unregistered version is not crippled in any way. It will only add a small note to your help topics to encourage you to be honest and to register the shareware you use.

These options are very interesting for Delphi and C++Builder developers:

•	If you are a component writer, use the Delphi Parser to build an outline help file for your component. Just fill in the spaces and you are done. HelpScribble can also extract the comments from your source file and use them as the default descriptions.

•	If you are an application writer, HelpScribble provides you with a property editor for the HelpContext property. You can select the topic you need from a list of topic titles or simply instruct to create a new topic. No need to remember obscure numbers.

•	The property editor also provides a tree view of all the components on your form and their HelpContext properties. This works very intuitively. (Much nicer than those help tools that simply mess with your .dfm files.)

•	HelpScribble can perform syntax highlighting on any Delphi source code in your help file.

HelpScribble is shareware, so feel free to grab your copy today from my web site at http://www.jgsoft.com/