1.2 Математическая модель предметной области
Опишем математическую модель предметной области, опираясь на теорию множеств:
введем понятие популяции. Популяция – это набор хромосом. Поэтому опишем популяцию следующим образом:
каждая хромосома является элементом популяции:
в свою очередь хромосома представляет собой набор генов:
;
где каждый ген представляет собой правило:
введем операцию мутации:
введем операцию кроссовера:
каждой хромосоме соответствует значение фитнесс-функции:
выбор лучшей хромосомы с максимальным значением фитнесс-функции:
введем отношение нестрогого порядка на множестве
:
и, наконец, операцию селекции:
1.3 Проектирование
1.2.1 Проектирование структур данных
Для решения поставленной задачи спроектируем необходимые классы.
Параметры генетического алгоритма должны задаваться пользователем, поэтому для хранения значений этих параметров создадим класс GAParametres. В нем будут храниться коэффициенты для операций мутации, скрещивания и селекции.
Также необходимо спроектировать классы для описания объектов генетического алгоритма. Основным объектом является хромосома, которая в нашем случае представляет набор правил, по которым строиться топология нейронной сети. Представим хромосому отдельным классом MyChromosome. Хромосома состоит из набора генов, каждый ген опишем классом MyGen. Каждый ген представляет собой одно правило. И поэтому поля данного класса будут отражать каждый пункт правила.
Таким образом, объект хромосома класса MyChromosome будет представлять собой массив объектов MyGen. В свою очередь хромосомы объединяются в популяцию. Для популяции генетического алгоритма создадим соответствующий класс Population. Объект этого класса будет содержать в себе список объектов класса MyChromosome. Класс Population будет включать в себя реализацию процесса эволюции.
Так как правила содержатся в каждой хромосоме в закодированном виде, то чтобы использовать правила для построения топологии нейронной сети, необходимо преобразовывать хромосому в набор правил. Для преобразования и хранения правил построим соответствующие классы ChangeTableItem и ChangeTable. ChangeTableItem представляет ген в расшифрованном виде, т.е. одно правило, а ChangeTable список ChangeTableItem. Т.о. класс ChangeTable хранит весь набор правил.
Каждое правило состоит из двух частей: условия, при выполнении которого, будет выполнена заданная в правиле операция, и сама операция. Для удобства представления правила создадим два класса Operation для описания операции и OperationCondition для описания условия операции. Класс Operation будет хранить описание всех возможных операций над графом, а класс OperationCondition представлять условия для их выполнения.
Важным моментом в генетическом алгоритме является вычисление фитнесс-функции хромосомы. Для описания фитнесс-функции в целом спроектируем класс PlanarGraphFitnessFunction. Этот класс будет описывать процесс вычисления фитнесс-функции в общем виде. Вычисление каждой конкнетной фитнесс-функции опишем классами, унаследованными от PlanarGraphFitnessFunction: TriangleMeshGraphFitnesFunction (вычисление фитнесс-функции для треугольной сетки), QuardicMeshGraphFitnesFunction (вычисление фитнесс-функции для квадратной сетки), HexMeshGraphFitnesFunction (вычисление фитнесс-функции для шестиугольной сетки) и BySampleGraphFitnesFunction (вычисление фитнесс-функции для заданного образца).
Так как для подсчета фитнесс-функции необходимо выполнить планаризацию графа, то для решения этой задачи спроектируем следующие классы: Planar, TwoDirectionWalker и Cycle.
Главным классом, отвечающим за весь процесс работы генетического алгоритма, и реализующим интерфейс пользователя является класс Genetic.
Диаграмма классов представлена на рисунке 1.12.