Генетический алгоритм в эксель
1 Михальцова Е.В., Московский государственный университет экономики, статистики и информатики Реализация генетического алгоритма для двумерных массивов с помощью VBA в Excel В статье описана реализация генетического алгоритма для целочисленных задач, решение которых представляет собой двумерный массив данных. Практическая реализация алгоритма осуществляется для конкретной постановки задачи с помощью VBA для Excel. В статье приводятся основные части программного кода, осуществляющие алгоритм. Существует целый ряд задач целочисленного программирования, решение которых фактически возможно только с помощью полного перебора, например, широко известная задача о назначениях при добавлении некоторых условий на переменные. В качестве примера рассмотрим следующую задачу. Распределяется m задач между n сотрудниками, каждая задача характеризуется длительностью выполнения для каждого сотрудника в днях d ij (i = 1..m, j = 1..n) и полезностью выполнения задачи z i (i=1..m). Общее время выполнения задач каждым из сотрудников не должно превышать t. Необходимо составить такую выборку задач, которая обладала бы наибольшей полезностью в рамках рассматриваемого периода t. Пусть x ij - псевдобулева переменная, принимающая значение 1 только в том случае, когда сотрудник j выполняет задачу i. Ограничение на распределение задач принимает вид: n j= 1 x 1 ( i ij = 1.. m) т.е. одна задача может выполняться не более чем одним сотрудником. Ограничение на время выполнения задач принимает вид: m i= 1 xij dij t ( j = 1.. n) Общее время выполнения задач каждым из сотрудников не превышает периода, на который составляется расписание. Функция полезности задается как: n m F x ij zi max (3) = j= 1 i= 1 (1) (2) 1
2 Необходимо найти такое распределение задач, которое суммарно давало бы наибольшую полезность с учетом важности и сроков завершения задач. Решение задачи реализуется с помощью генетического алгоритма. Алгоритм состоит из следующих частей: отбор множества решений (популяции), генерация новых решений как различных комбинаций частей решений популяции, используя отбор, рекомбинацию (кроссинговер) и мутацию. В качестве решений используются матрицы X = (x ij ) (i = 1..m, j = 1..n), сопоставляющие задачи i с исполнителями j. В качестве целевой функции F используется функция (3). Ограничение (1) выполняется при формировании решений, единица может проставляться только для одного значения j. Ограничение (2) учитывается после формирования столбцов матриц X. Из столбцов, в которых ограничение не выполняется случайным образом вычеркиваются единицы до выполнения условий ограничения. При формировании матрицы X возможно учитывать также и другие ограничения на вид переменных, например, назначение задач только тем сотрудникам, которые обладают необходимой квалификацией, учет загруженности сотрудников на других проектах, учет сменности работы и т.д. Для реализации алгоритма использованы возможности VBA и Excel. Excel используется в качестве хранилища и средства визуализации данных, параметры алгоритма и входные данные также задаются в Excel. Расчет производится с помощью макроса, описание которого приведено ниже. В качестве параметров алгоритма выделены следующие: Размер начальной популяции; Количество особей в элитном отборе; Количество итераций генерации новых решений. Параметры алгоритма и сведения об исходных данных задаются на листе «Параметры» в Excel (Рисунок 1). Рисунок 1. Задание параметров задачи Исходные данные для решения задачи располагаются на листе «Задачи на период планирования» (Рисунок 2). 2
3 Рисунок 2. Исходные данные задачи Матрица длительности реализации задач для каждого из сотрудников задается на листе «Матрица длительности» (Рисунок 3). Рисунок 3. Матрица длительности выполнения задач Сам расчет осуществляется на листе «Популяция». В статье приведены наиболее важные части макроса, осуществляющие алгоритм. Решением в данном алгоритме является матрица, в строках которой указываются номера задач, а в столбцах номера сотрудников. Элементами матрицы являются нули или единицы, при этом в строке матрицы может находиться не более одной единицы. Формирование каждого решения алгоритма предусматривает следующую последовательность действий: 1. Формирование нумерации исполнителей в столбцах матрицы решения. Здесь n количество сотрудников, k номер первого столбца решения на листе Excel. Sheets("Популяция").Cells(4, k j).value = j 2. Генерация случайным образом значений матрицы. Генерация осуществляется по строкам матрицы, случайным образом выбирается сотрудник, которому назначается (проставляется единица) или не назначается (проставляется ноль) задача, остальным сотрудникам 3
4 проставляются нули. Перед использованием Rnd() необходимо инициализировать генератор случайных чисел (оператор Randomize). Здесь n и k аналогичны предыдущему пункту. For i = 1 To m z = Round((n * Rnd()), 0) If Sheets("Популяция").Cells(4, k j).value = z Then Sheets("Популяция").Cells(i + 4, k j).value = 1 Else Sheets("Популяция").Cells(i + 4, k j).value = 0 3. Расчет длительности и веса выполняемых задач по сотрудникам. Здесь n и k аналогичны предыдущим пунктам, m количество задач. Sheets("Популяция").Cells(m + 5, k j).value = Sheets("Популяция").Cells(m + 5, k j).value + Sheets("Популяция").Cells(i + 4, k j).value * Sheets("Матрица длительности").cells(i + 1, 1 + j).value Sheets("Популяция").Cells(m + 6, k j).value = Sheets("Популяция").Cells(m + 6, k j).value + Sheets("Популяция").Cells(i + 4, k j).value * Sheets("Задачи на период планирования").cells(i + 2, 7).Value 4. Проверка выполнения условия на общую продолжительность выполнения задач каждым сотрудником. Проведение корректировки решения. Здесь n, k и m аналогичны предыдущим пунктам, z случайный номер задачи, для которой производится корректировка. d = 0 Do While d = 0 If Sheets("Популяция").Cells(m + 5, k j).value > Sheets("Параметры").Cells(10, 2).Value Then z = Round(((m - 1) * Rnd() + 1), 0) Sheets("Популяция").Cells(z + 4, k + j - 1).Value = 0 Sheets("Популяция").Cells(m + 5, j k).value = 0 Sheets("Популяция").Cells(m + 6, j k).value = 0 For i = 1 To m Sheets("Популяция").Cells(m + 5, j k).value = Sheets("Популяция").Cells(m + 5, j k).value + Sheets("Популяция").Cells(i + 4, k j).value * Sheets("Матрица длительности").cells(i + 1, 1 + j).value 4
6 Оставшиеся элементы первоначальной популяции формируем отдельно и в случае, если целевая функция (суммарный вес) нового сформированного элемента превышает минимальный суммарный вес элементов элитного отбора новый сформированный элемент заменяет элемент с минимальным суммарным весом. Здесь n, m, k, p и l аналогичны предыдущим пунктам, p1 количество элементов в начальной популяции. For t = (p + 1) To p1 l = l + 1 k = k + n + 1 i = SForm(k, l) z = 1 For j = 1 To p If Sheets("Популяция").Cells(2, z + 1).Value > Sheets("Популяция").Cells(2, j + 2).Value Then z = j + 1 If z <> p + 1 Then Sheets("Популяция").Cells(1, z + 1).Value = Sheets("Популяция").Cells(1, p + 2).Value Sheets("Популяция").Cells(2, z + 1).Value = Sheets("Популяция").Cells(2, p + 2).Value For i = 1 To m + 2 Sheets("Популяция").Cells(i + 4, (z - 1) * (n + 1) j).value = Sheets("Популяция").Cells(i + 4, p * (n + 1) j).value Next i Next t Второй этап алгоритма состоит из следующих шагов: 1. Выбор родительской пары из особей элитного отбора составляем все возможные пары. 2. Кроссинговер для каждой родительской пары берем случайную строку l матрицы X (l =0..m). Все строки матрицы с индексами 1..l-1 новой особи (потомка) заполняем элементами строк с теми же индексами, но из матрицы X первой родительской особи. Остальные строки заполняются из матрицы второй родительской особи. Для второго потомка делается наоборот - элементы 1..l- 1берут от второго родителя, а остальные от первого. 3. Мутация новые особи с вероятностью 5% мутируют для каждой матрицы выбирается случайная строка и заново генерятся значения в произвольном порядке. 4. Лучшую из полученных особей-потомков добавляем в популяцию взамен самой плохой старой особи при условии, что значение 6
8 Sheets("Популяция").Cells(i + 4, (t - 1) * (n + 1) j).value = Sheets("Популяция").Cells(i + 4, (p + 2) * (n + 1) j).value Next i Else Exit Function Алгоритм выполняется либо заданное число раз, либо до тех пор, пока новое полученное решение будет не лучше, чем имеющиеся в элитной выборке. Полученные в результате реализации алгоритма решения представлены на рисунке 4. Рисунок 4. Результаты расчета алгоритма Результатом алгоритма является набор матриц Х, элементы которых образуют оптимальные приближенных решений. В рассматриваемой задаче целью является не нахождение всех оптимальных решений, а нахождение любого из них. Поэтому первое решение с максимальным суммарным весом примем как решение поставленной задачи. В данной статье охвачена только реализация генетического алгоритма. Сама задача шире в рамках ее решения осуществляется выбор параметров задачи из исходных данных, осуществляется оптимизация, составление календарного плана работ и корректировка составленного плана с учетом сделанных вручную исправлений. Предложенная реализация генетического алгоритма позволяет находить приближенные оптимальные решения для задач, переменные которых представляют двумерный массив данных с ограничениями на значения элементов массивов. Алгоритм также позволяет оставлять решения, не удовлетворяющие ограничениям задачи в популяции путем проведения корректировки данных решений. Данное усовершенствование позволяет быстро находить решения для задач, большинство случайным образом составленных решений которых не попадает в ограничения задачи. 8
Генетический алгоритм — это один из методов решения задач, который разработан на основе эволюции. Такой алгоритм используют тогда, когда количество решений настолько большое, что протестировать их все нереально. Расскажем, как устроены эти алгоритмы, и почему с ними нейросети работают на порядок лучше.
Эволюция в математике
Составление алгоритма начинается с создания реестра моделей — популяции . Причем каждая модель должна быть представлена набором чисел — генов. Этот набор генерируют случайным образом.
Список решений — это и есть популяция. Из нее выбираются самые жизнеспособные модели для следующей популяции. Этот процесс многократно запускается до тех пор, пока не будет найдено оптимальное решение.
Чтобы понять, насколько качественным вышло решение, применяют функцию приспособленности. Например: F-score и точность предсказания. Чем качественнее решение, тем больше шансов, что особь будет отобрана для следующей популяции.
Анализ данных не останавливается на Excel. Пройдите онлайн-курс «Google Таблицы для бизнеса ». Научитесь работать с Google Таблицами с любого устройства, синхронизируйте вашу работу с коллегами и интегрируйтесь с Google Forms и Google Analytics.
Основные стадии
После того, как будет создана первая популяция, алгоритм проходит четыре стадии:
1. Отбор.
Смысл отбора в том, чтобы найти самые жизнеспособные модели и передать их гены следующему поколению. Приспособленность — главное качество, по которому отбирают родителей. Причем количество родителей (пар особей) может быть любым, но всегда одинаковым для каждого последующего цикла.
Есть два основных метода отбора::
- Ранговый. Популяцию делят на несколько рангов (групп). Ранги назначают на базе функции приспособленности. А затем пропорционально отбирают по несколько особей из каждого ранга.
- Турнирный. Несколько особей выбирают случайным образом. Из отобранной группы выделяют лучших. Процесс повторяют до тех пор, пока не наберут нужное число особей из этой популяции.
У каждого метода свои плюсы. Ранговый помогает сохранить разнообразие особей. Турнирный подходит тогда, когда модели можно сравнивать только попарно, а выражение функции приспособленности числом недоступно. Например, его используют для игровых стратегий.
2. Скрещивание.
На этой стадии происходит обмен информацией между родителями. Из популяции отбирают пары особей и смешивают отдельные фрагменты их хромосом. В результате получается новый набор генов.
Часто применяют метод одноточечного скрещивания — внутри хромосом родителей выбирают случайное место и разделяют каждую из них на две части. Далее эти части меняют местами, а затем новые данные загружают в популяцию.
3. Мутация.
Запускается редко и в случайном порядке переставляет местами числа отдельных генов (например: меняет 1 на 0).
Мутация способствует сохранению разнообразия внутри популяции. При этом степень приспособленности мутировавшей особи может повыситься, а может понизиться.
4. Завершение алгоритма.
Процесс заканчивается тогда, когда новая созданная популяция почти не отличается от предыдущей. Это означает, что полученное решение оптимально.
Генетические алгоритмы или нейросети: что лучше
Алгоритм идеально работает с большим объемом дискретных данных, так как простой перебор занимает на порядок больше времени.
Data scientist Мишель Берк запрограммировал алгоритм расставить в верном порядке буквы зашифрованного предложения: Genetic Algorithms are wild. Алгоритму потребовалось сделать выбор из всех вероятных комбинаций — 2753. У него было 30 особей в популяции, а решил задачу он на 51-м поколении. Для этого ему пришлось проверить 1 530 комбинаций.
Алгоритм может быстро найти кратчайший путь между двумя точками. Поэтому его применяют для построения маршрутов GPS-систем и расчета траектории движения.
Для расчета распространения коронавируса ученые также воспользовались генетическим алгоритмом. На его базе был проведен анализ распространения инфекции в 40 странах мира.
Нейросети лучше работают с непрерывными данными. Так они лучше понимают языки или распознают изображения. А еще нейросети используют для задач линейной регрессии, когда нужно найти зависимость между переменными.
Мы разработали онлайн-курс «Excel для финансов» для тех специалистов, которым нужно быстро и качественно составлять отчеты в Excel. Вы научитесь рассчитывать зарплаты сотрудников, готовить налоговую и финансовую отчетность. После курса ваша работа с данными в Excel станет намного эффективнее.
Алгоритмы и нейросети в симбиозе
Существуют примеры удачного объединения нейросетей и алгоритмов в одной системе.
Так алгоритмы могут оптимизировать функциональность модели. Например: подобрать вес, функцию активации. Но их использование для подбора требует больших затрат времени и вычислительных мощностей. Например: чтобы научить нейросети обыгрывать реальных людей в видеоиграх.
Так в 2017 году OpenAI применила алгоритм, для отбора тех ботов в игру Dota 2, которые выигрывали матчи. А затем они провели обучение нейросетей на основе этих данных.
Узнать подробнее об обучении в геймдеве можно тут.
Хотите узнать больше? Подписывайтесь на каналы и соцсети онлайн-школы robot_dreams:
Помогите пожалуйста написать алгоритм для кнопки "Решение".
при нажатии на кнопку на второй странице должна появляться матрица которая создается по следующему условию.
По оси Y это узлы, по оси X ветки, если ветка входит в узел,то ячейка равна 1, выходит -1, не связаны никак = 0, каждая строка это узел,а столбец ветка.Остальные ячейки остаются незаполнены вокруг матрицы
на первой страницы их взаимосвязь в столбцах H,J,K. Увых-это ветка выходит из узла, Увх-входит в него. Узел ) никак не надо учитавать,начало с 1го узла.Предел матрицы 200*200
Генетический алгоритм для составления расписания
В генетическом алгоритме для составления расписаний что берется в качестве особи, хромосомы и гена.
Генетический алгоритм для составления расписания
Здравствуйте. В генетическом алгоритме для составления расписаний что берется в качестве особи.
Алгоритм составления расписания
какой из алгоритмов можно применить к решению следующей задачи Дано: 1. Множество операций.
Написать программу для составления матрицы, элементами которой будут числа, равные количества цифр в одноименной ячейке в массиве А.
Задан двумерный массив А = (aij), где i = 1,2 . k, j = 1,2 . f, элементами которого являются.
Извините,лучше смотрите этот файл,в том я просто делал но при помощи функции "Если",а надо при помощи кнопки
Алгоритм составления вложенного меню
Здаров всем! Надо правильно составить БД. Вопрос в чем то похож на предыдущую тему (по этой теме и.
Алгоритм составления школьного расписания
субж! если кто-н знает или были первые попытки осуществить - то пишите!
Алгоритм составления расписания матчей
Добрый день! Озадачился созданием расписания матчей (в частности по футболу) и вот что у меня.
Алгоритм составления футбольного календаря
нужна помощь в написании алгоритма составления футбольного календаря. на вход подается список.
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.
Please Note: With Office 2010, Excel’s Solver add-on actually includes a genetic algorithm (evolutionary) solver. You can read more about it here .
Introduction
Genetic algorithms (GAs) are based on biological principles of evolution and provide an interesting alternative to “classic” gradient-based optimization methods. They are particularly useful for highly nonlinear problems and models, whose computation time is not a primary concern. Continuity of functions is not required. Similar to other methods such as Simulated Annealing, they perform better than gradient-based methods in finding a global optimum if a problem is highly nonlinear and features multiple local minima. In general, GAs approach the entire design space randomly and then improve the found design points by applying genetics-based principles and probabilistic selection criteria. Although a large number of modified algorithms are available, a GA typically proceeds in the following order:
- Start with a finite population of randomly chosen chromosomes (“design points”) in the design space. This population constitutes the first generation (“iteration”).
- Evaluate their fitness (“function value”).
- Rank the chromosomes by their fitness.
- Apply genetic operators (mating): reproduction (reproduce chromosomes with a high fitness), cross-over (swap parts of two chromosomes, chosen based on their fitness to create their offspring) and mutation (apply a random perturbation to parts of a chromosome). All of these operators are assigned a probability of occurrence.
- Assemble the new generation from these chromosomes and evaluate their fitness.
- Apply genetic mating as before and iterate until convergence is achieved or the process is stopped.
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
Quick Start Tutorial – This document will get you going with the software. It will be included in the next revision as a help file.
Paper: “Thermal and Structural Stud-Wall Optimization in Excel using Genetic Algorithms” – This document shows some verification calculations (also provided in the download) and explains parameters and settings a bit more in detail.
Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Доронин В.А.
Использование таблицы Microsoft Excel в качестве источника данных приложения Microsoft. Net Framework
Профилирование и оптимизация кода приложения для построения поверхности функции двух переменных на языке Python
Текст научной работы на тему «Реализация генетического алгоритма для задач классификации»
Реализация генетического алгоритма для задач классификации
Московский институт электроники и математики, каф. ИТАС
В настоящее время наиболее распространенным является в подход по применение технологии объектно-ориентированного программирования (ООП), который позволил реализовать Генетический Алгоритм (ГА) средствами среды 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
MyDB. ConnectionString = "Provider=MicrosoftJet.OLEDB.4.0;
На этапе инициализации исходных данных для ГА пользователю предлагается проставить исходные признаки самостоятельно или воспользоваться набором сформированных признаков по умолчанию из БД. Для наглядного представления внутренних процессов работы ГА реализован графический интерфейс:
Графическое представление исходных признаков - точек и квадратных областей-особей реализовывалась стандартным средством среды 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
Штрихование внутренних областей квадратов происходит при последовательном переборе всех особей каждого класса с простановкой соответствующего для класса цветом: Me.Picturel.FillStyle = 3+j. Координаты особей задаются случайным образом: Gen.corMinX = Int((Me.Picture1.Width + 1) * Rnd)
Доступ к БД производится с помощью технологии 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 были реализованы методом комбинирования и подстановок:
strSQL = "SELECT Count(*) AS Qr FROM tmpObj WHERE ClassObj = " & Str(k1) & " AND (curX >= " & Str(Gen.corMinX) & _ " AND curX
Реализацию ГА можно представить в виде следующей последовательности шагов:
■ Инициализация: создание заданного числа популяций. Заполняются все свойства класса 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
Set rv = New Rij // в нашу область вошли следующие точки rstC.Open "Select Count(*) As Qr From tmpObj Where ClassObj = " & Str(k1) & " And (curX >= " & Str(Gen.corMinX) & " And curX = " & Str(Gen.corMaxY) & ")", MyDB, adOpenDynamic, adLockOptimistic rstC.MoveFirst rv.valRij = rstC("Qr")
Gen.F = Gen.F + rv.valRij // всего точек в области Gen.Rijs.Add rv // сохраняем кол-во точек 1 класса, потом 2 класса Next k1
If Gen.F = 0 Then Gen.F = 0 Else
На заключительном шаге работы ГА генерирует логические закономерности в терминах элементарных событий и определяет их точность и полноту (кол-во точек в диапазоне / общее кол-во точек в данном классе):
Графически отображает элементарные события следующий программный
В качестве примера расчета целевой функции
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 г.
3. Джеймс Р. Грофф, Пол Н.Вайнберг. Полное руководство SQL Второе издание. BHV "Ирина", Киев. 2001
Читайте также: