Главная › Новости

Реализация генетического алгоритма

Опубликовано: 22.08.2018

20: Введение в генетические алгоритмы (1 из 2)

Страница 1

Классы, имеющие отношение к реализации ГА в основном сосредоточены в пространстве имен GeneticClasses, схематически показанном на диаграмме классов (Рис.2.2.).

Рис.2.2. Диаграмма классов пространства имен GeneticClasses

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

public interface IChromosome

{FitnessFunctionValue{get;set;}CrossOver(IChromosome chr);Mutate(double p); // p - вероятность мутацииInversion(double p); // p - вероятность инверсии

}

Вполне очевидны элементы этого интерфейса, соответствующие основным терминам ГА.

Класс BinChromosome (реализует интерфейс IChromosome) реализует «классическую» хромосому, использующую бинарное кодирование фенотипа. Закрытыми переменными этого класса являются:

protected double fitnesFunctionValue;bool[] allels;PhenoGeno phenoGeno;double[] phenoAtributes;

Следует отметить подход к определению значения функции приспособленности (переменная fitnesFunctionValue). Исходя из теории ГА - это «внешняя» по отношению к ГА функция из «реального мира». Для обеспечения высокого уровня универсальности можно было бы передавать в класс BinChromosome переменную функционального типа (делегат в C#). Однако это привело бы к некоторым потенциальным проблемам: избыточность вычислений и сложность в определении универсальной сигнатуры такой функции.

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

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

Переменная alleles представляет бинарный массив - генотип хромосомы.

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

Это объект класса PhenoGeno, который содержит в себе массив объектов PhenoGenoTriada. Каждый такой объект содержит диапазон и точность кодировании (переменные a, b, и resolution). Используя эти данные и входной параметр-фенотип X метод Pheno2Geno осуществляет его преобразование во фрагмент генотипа - бинарныймассив. Метод Geno2Pheno осуществляет обратное преобразование.

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

Класс BinChromosome реализует интерфейс IChromosome для поддержки хромосом с вещественным кодированием. Переменные этого класса:

private string id; //идентификатор хромосомыdouble fitnessFunctionValue;double[] phenoAttributes;double from;double to;double alpha; //параметр BLX-кросовера

Для удобства наблюдения за ходом ГА в клиентских приложениях, в классе BinChromosome присутствует текстовый идентификатор id хромосомы, который закрытая функция MakeID генерирует как строку с высокой вероятностью уникальности.

Массив phenoAttributes соответствует фенотипу особи.

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

Переменная alpha - это коэффициент, характеризующий реализацию кроссовера для РГА.

Генетические операторы реализованы в классе BinChromosome следующим образом (см. Глава 2, стр.20-21)

кроссовер - BLX-a кроссовер;

мутация - случайная мутация Михалевича

Для обслуживания ГА удобно определить служебный класс Population, реализующий полезные функции популяции в целом. Здесь важно отметить 2 факта:

класс содержит множество особей в отсортированном в порядке возрастания функции приспособленности списке species;

класс поддерживает переменную fitnessSum, которая хранит суммарное значение функций приспособленностей особей.

Соответственно этому метод Add добавления особи в популяцию сохраняет отсортированное состояние списка species и актуальное значение переменной fitnessSum.