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

§ Фиксированная разрядность генов.

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

§ Ограничений на тип кроссовера и мутации нет.

§ Случайный обмен особями между "островами". Если миграция будет слишком активной, то особенности островной модели будут сглажены, и она будет не очень сильно отличаться от моделей ГА без параллелизма.

5. CHC (Eshelman)

CHC расшифровывается как Cross-population selection, Heterogenous recombination and Cataclysmic mutation. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, используются популяции небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями, и между их потомками. В силу этого после нахождения некоторого решения алгоритм перезапускается, причем лучшая особь копируется в новую популяцию, а оставшиеся особи подвергаются сильной мутации (мутирует примерно треть битов в хромосоме) существующих и поиск повторяется. Еще одной специфичной чертой является стратегия скрещивания: все особи разбиваются на пары, причем скрещиваются только те пары, в которых хромосомы особей существенно различны (хэммингово расстояние больше некоторого порогового плюс возможны ограничения на минимальное расстояние между крайними различающимися битами). При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover) - это разновидность однородного кроссовера, но в нем к каждому потомку попадает ровно половина битов хромосомы от каждого родителя. Таким образом, модель обладает следующими свойствами:

§ Фиксированный размер популяции.

§ Фиксированная разрядность генов.

§ Перезапуск алгоритма после нахождения решения.

§ Небольшая популяция.

§ Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных отличий.

§ Отбор в следующее поколение проводится между родительскими особями и потомками.

§ Используется половинный однородный кроссовер (HUX).

§ Макромутация при перезапуске.

Практическая часть

В данной курсовой работе приведен пример программы использующей генетический алгоритм. Программа создана посредством среды программирования Delphi 7 с использованием библиотеки компонентов GeneBase 2.0. Алгоритм компонента представляет собой применение методов, известных в теории эволюции, для эвристического поиска решений переборных задач.

Принцип работы программы

Сразу при запуске программы еще перед прорисовкой окна выполняется процедура FormCreate в которой производится инициализация внутренних переменных, инициализация интерфейса и прорисовка изображения. Прорисовка изображения проходит в процедуре CreateImage в два этапа: сначала необходимо рассчитать образ на экране при помощи одной из трёх целевых функций; и только после этого производится прорисовка посредством пикселей канвы объекта.

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

После выбора параметров нажатие на кнопку «Пуск алгоритма» приведет к запуску основной процедуры программы btnStartClick. В первые моменты выполнения программы происходит считывание установленных параметров в переменные и поля объекта GA1, который является прототипом класса TgeneticAlgorith, тем самым этому объекту задаются основные параметры для дальнейшей работы методов объекта. Затем вызывается метод Init объекта GA1 в который производит начальную инициализацию особей, используемых в генетическом алгоритме, случайными значениями. Переменные xCnt и xMaxCnt предназначены для отслеживания ситуации останова алгоритма. Переменная xOldS содержит значение приспособленности предыдущей, лучшей особи популяции. Затем запускается основной цикл программы и в нем, после проверок возможных ситуаций останова алгоритма, вызывается процедура OneEpoch объекта frmMain, в которой вызывается метод OneEpoch объекта GA1. Вызов данного метода приводит к выполнению одного шага генетического алгоритма. При этом производится вычисление приспособленности всех особей из популяции, а на основании этих данных формируется новая популяция. Далее происходит сравнивание приспособленностей: лучшего индивида текущей и предыдущей популяций и в случае малого различия наращивается переменная xCnt, а в противном случае – обнуляется. Затем обновляется переменная xOldS и выводятся основные значения лучшей особи текущей популяции.

Листинг программы

unit fmMain;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

ExtCtrls, StdCtrls, genetic, math;

type

TTargetFunction = function(X1,X2 : double):double;

TfrmMain = class(TForm)

Panel1: TPanel;

Panel2: TPanel;

GroupBox1: TGroupBox;

GA1: TGeneticAlgorith;

Label1: TLabel;

edtChromosomeCount: TEdit;

Label2: TLabel;

cbxGeneDegree: TComboBox;

Label3: TLabel;

edtCrossoverP: TEdit;

Label4: TLabel;

edtMutationP: TEdit;

Label5: TLabel;

edtInversionP: TEdit;

Label6: TLabel;

Label7: TLabel;

cbxOptimizeMethod: TComboBox;

Label8: TLabel;

cbxFunction: TComboBox;

imgFunction: TImage;

btnStart: TButton;

chbUseElitism: TCheckBox;

GroupBox2: TGroupBox;

Label9: TLabel;

Label10: TLabel;

stxTarget: TStaticText;

stxX: TStaticText;

stxY: TStaticText;

Label11: TLabel;

Label12: TLabel;

edtMaxCount: TEdit;

Label13: TLabel;

btnStop: TButton;

procedure FormCreate(Sender: TObject);

function GA1GetSutability(

Chromosome: TChromosome): Double;

procedure btnStartClick(Sender: TObject);

procedure cbxFunctionChange(Sender: TObject);

procedure btnStopClick(Sender: TObject);

private

{ Private declarations }

fTarget : TTargetFunction;

fImage : TBitmap;

public

{ Public declarations }

StopFlag : boolean;

procedure CreateImage;

property Target : TTargetFunction read fTarget write fTarget;

procedure OneEpoch;

end;

var

frmMain: TfrmMain;

xBmp : array [0 99,0 99] of double;

implementation

var

fMinX,fMaxX,fMinY,fMaxY : double;

{$R *.DFM}

function De_Jong_5(X1,X2:double):double;

var

J : integer;

xS1,xS2 : double;

begin

fMinX := -65.536;

fMinY := -65.536;