Генетический алгоритм в эксель

Обновлено: 06.01.2025

Текст научной работы на тему «Реализация генетического алгоритма для задач классификации»

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

Московский институт электроники и математики, каф. ИТАС

В настоящее время наиболее распространенным является в подход по применение технологии объектно-ориентированного программирования (ООП), который позволил реализовать Генетический Алгоритм (ГА) средствами среды Visual Basic (VB). Программные модули работы ГА создаются в определенных классах и компилируются в библиотеку ActiveX DLL. После компиляции программный алгоритм ГА становится доступным для других разработчиков, при этом исключается потребность перекомпиляции всего исходного блока кода программы. Основная работа ведется с экземплярами таких классов - объектами. Каждый класс представляет собой шаблон, по которому создаются объекты нужного типа: родители, потомки и объекты, хранящие параметры работы алгоритма. Важной особенностью ООП - подхода является многократно используемый программный код. В основном многократное использование объекта обеспечивается его интерфейсом, т.е. его методами и свойствами, посредством которых наши объекты взаимодействуют с окружающим миром. Построение объектов с хорошо продуманным интерфейсом, в дальнейшем при необходимости изменения его внутренней функциональности позволит добавить новый интерфейс, никоем образом не повлияв на другие объекты, которые работают с изменяемыми объектами программы.

Для реализации ГА была разработана следующая система классов:

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

■ ClassesObjects, ClassObject - коллекция и класс. Содержат описания классов объектов, для которых формируются правила.

■ ObjectslnClass, ObjectlnClass - коллекция и класс. Содержит описание объектов, входящих в класс объектов.

■ Genoms, Genom - коллекция и класс. Содержит описание особей, входящих в популяцию.

■ gParents, gParent - коллекция и класс. Содержит описание родительских особей.

Размерность задачи, числовые диапазоны, начальный объем популяции, вероятность скрещивания и вероятности мутаций, а также условия завершения работы ГА задаются на начальных этапах загрузки программы ГА. При этом пользователь может изменять значения параметров по умолчанию на необходимые. Исходные параметры для работы ГА, промежуточные результаты и итоговые результаты работы программы сохраняются в Базе Данных (БД) MS Access.

При первом вызове программы пользователю предлагается самостоятельно произвести поиск БД - произвести ее подключение к проекту. Путь к открываемой БД сохраняется в БД, при последующем запуске программы местонахождение БД будет заполняться автоматически. Для реализации диалогового окна общения с пользователем использовалось стандартное средство среды VB - CommonDialog. Подключение к Jet-машине происходит по строчной команде. Подключение к БД через 32-битный источник данных ODBC в программе предусмотрено. В качестве примера подключения к БД может служить следующий программный код:

Public MyDB As New ADODB.Connection

На этапе инициализации исходных данных для ГА пользователю предлагается проставить исходные признаки самостоятельно или воспользоваться набором сформированных признаков по умолчанию из БД. Для наглядного представления внутренних процессов работы ГА реализован графический интерфейс:

Графическое представление исходных признаков - точек и квадратных областей-особей реализовывалась стандартным средством среды VB. Принадлежность к классу определяется цветом. Примером процедуры обработки событие MouseDown стандартного элемента управления РшШгеВох может служить ниже приведенный программный код: Me.Picture1.DrawWidth = 5

Me.Picture1.PSet (X, У), RGB(ObCl.rRGB, ОЬС1^В, Obа.bRGB).

Данный код позволяет проставлять признаки щелчком клавиши мыши. Функция RGB возвращает цвет точки на PictureBox, ее параметры - свойства объекта. Для графического отображения особей использовались квадраты:

Me.Picture1.Line (Gen.corMinX, Gen.corMaxY)-(Gen.corMaxX, Gen.corMinY),

RGB(cOB.rRGB, cOB.gRGB, cOB.bRGB), B

Доступ к БД производится с помощью технологии ADO (ActiveX Data Object). Работа с ADO осуществляется через элементы управления данными и объектный интерфейс. Все манипулирования данными производятся только через объекты и в программном коде. В зависимости от типа запроса к данным разработана процедура открытия набора записей:

.ActiveConnection = curCon .Source = strSQL If ReadOnly = True Then

.CursorType = adOpenStatic .LockType = adLockReadOnly .CursorLocation = adUseClient

.CursorType = adOpenDynamic .LockType = adLockOptimistic .CursorLocation = adUseServer

В зависимости от переменной ReadOnly записи открываются либо для чтения, либо с полным набором разрешений на изменение данных. При открытии производится манипулирования курсором и возвращаемым набором (привязкой к данным).

Для получения хранимой информации из БД использовался язык структурированных запросов SQL. При реализации ГА запросы на SQL были реализованы методом комбинирования и подстановок:

Реализацию ГА можно представить в виде следующей последовательности шагов:

■ Инициализация: создание заданного числа популяций. Заполняются все свойства класса ClassesObjects. Инициализация класса Genoms случайным образом. Занесение исходных данных в БД. Графическая прорисовка особей и признаков.

■ Шаг2. Выполнить операцию миграции из каждой популяции j. Происходит перенос генов из одной популяции в другую.

■ Шаг3. В каждой популяции сократить число особей до K (оператор редукции) - все особи с наименьшим значением целевой функции, при этом вся коллекция класса Genoms перебирается последовательно. При удалении элементов коллекции класса используется метод коллекции remove. Графическая прорисовка особей и признаков.

■ Шаг4. Если выполнятся условие останова - перейти к шагу 9, иначе выполнить следующий шаг.

■ Шаг5. Если размеры популяции меньше чем заданные, выбрать родительские пары для оператора скрещивания, иначе перейти к шагу 7. Заполнение коллекции gParents.

■ Шаг6. Выполнить оператор скрещивания. Обмен генами: minX,minY и maxX,maxY между родителями. Обновление исходного множества. Перейти к шагу 5. Занесение результатов в БД. Графическая прорисовка особей и признаков.

■ Шаг7. Выполнить оператор мутации - изменение с заданной долей вероятности одного из генов: minX,minY,maxX или maxY. Графическая прорисовка особей и признаков. Перейти к шагу 2.

■ Шаг8. Формируется множество КП. Занесение результатов в БД. Завершением работы ГА может служить показатель наличия правил с точностью и полнотой >=0.9

■ Шаг9. Осуществляется преобразование сохраненных кодовых

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

рассмотреть следующий программный блок: Gen.F = 0 // всего точек

For k1 = 1 To ClOb.ClassesObjects.Count // всего классов 2

If Gen.F = 0 Then Gen.F = 0 Else

На заключительном шаге работы ГА генерирует логические закономерности в терминах элементарных событий и определяет их точность и полноту (кол-во точек в диапазоне / общее кол-во точек в данном классе):

1. Если 7 < XI < 10 И 5 < Х2 < 9, ТО Класс1 (точность - 1, полнота - 0.5)

2. Если 1 < Х1 < 3 И 1 < Х2 < 6, ТО Класс1 (точность - 0.77, полнота - 0.44)

3. Если 1 < Х2 < 6, ТО Класс1 (точность - 0.58, полнота - 0.88)

Графически отображает элементарные события следующий программный

В качестве примера расчета целевой функции

genF = Gen.F Set rv = New Rij

Set rv = Gen.Rijs.Item(jl) // точка нужного класса j1 = 1 Gen.F = rv.valRij / genF

Результатом данной работы является программная реализация ГА с применением коллекций, в рамках методологии ООП, комбинированных запросов и стандартных средств среды Visual Basic. Программная реализация ГА позволила генерировать логические закономерности в терминах элементарных событий с определением точности и полноты для каждого правила.

1. Солодовников И.В., Доронин В. А. Генетический алгоритм для поиска логических закономерностей в данных - // Информационные технологии в управлении. № 7. М.: 2005 г.

2. Сайлер Б., Споттс Д. Специальное издание. Использование Visual Basic 6. Вильямс. 2000 г.

This software allows the user to take an Excel spreadsheet with any type of calculation data (no matter how complex) and optimize a calculation outcome (e.g. total cost). This is based on the selection of up to five design variables and up to five constraints. The optimization can be performed as a maximization, minimization or the attempt to reach a target value. Applications for this technique lie in every field of work. If the problem can be modeled in Excel, it can be optimized using this program.

The main advantage of this program over the Solver, which is supplied with Excel is that it can solve highly nonlinear problems or problems that feature discontinuous functions. Both of these can be problematic for the gradient-based optimization routine that Solver is based on. The software available here is the result of a term project in a class on engineering design optimization. It was written for research and should only be used for that purpose since it may contain bugs (please report any bugs to me using the contact form). It has sufficient capability for small projects and study examples. See below for the specs.

This software is provided free of charge. Two working examples have been included with the installer. Please read the terms of the license that is provided with the software before using it. This current version (v. 1.2) replaces the earlier one that was available from this site.

Introduction

A Windows user interface was created for the GA routine, which allows the user to easily use the GA model without much prior knowledge. As can be seen in the screen shots, an Excel file, which contains the calculation model, can be selected and cell references for the function value, all design variables and all constraints can be specified. On another tab, the user can modify the given GA parameters and then on a third tab, the user can run the GA algorithm and capture its output. Optionally, the user can save all GA and model parameters to a text file and restore them from there later.

Downloads

Читайте также: