Общий алгоритм работы генетического алгоритма

Содержимое рюкзака представляется в виде хромосом или бинарных строк, i-й бит которых равен 1 если предмет положен в рюкзак, и нулю - в случае его отсутствия. Задается целевая функция S – вместимость рюкзака. Отбор осуществляется следующим образом:

1) Создание случайной популяции двоичных хромосом.

2) Оценка каждой из них.

3)

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

Отбор на основе полученных чисел.

4) Скрещивание полученных на третьем этапе хромосом.

5) Мутация.

6) Переход на второй шаг.

Алгоритм прерывается после заданного числа итераций. Блок схема работы алгоритма представлена на рисунке 3.

Рисунок 3 – Бблок-схема генетического алгоритма

3

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

Программное конструирование

Обоснование выбора языка программирования

Появление технологии .NET повлекло за собой массовую реконструкцию некоторых языков программирования, стремящихся использовать те или иные возможности платформы, такие как C++ и VisualBasic. Microsoft решили предложить разработчикам альтернативу – язык, ориентированный специально .NET и создали C#. Сами разработчики языка описывают его, как простой, современный, объектно-ориентированный и безопасный язык программирования. Синтаксически C# напоминает C++ и Java, что позволило программистам за достаточно короткое время изучить тонкости нового языка.

Несмотря на то, что C# и .NET предназначены в первую очередь для веб-разработки, их также активно применяют для создания приложений, которые должны устанавливаться на машине конечного пользователя, где и будет выполняться вся обработка данных. Разработку таких приложений обеспечивает библиотека WindowsForms, позволяющая проектировать графический интерфейс. Система, описанная в данной работе, разработана именно с помощью библиотеки WindowsForms.

1) Язык программирования C# претендует на подлинную объектную ориентированность.

2) Язык программирования C# призван реализовать компонентно-ориентированный подход к программированию, который способствует меньшей машинно-архитектурной зависимости результирующего программного кода, большей гибкости, переносимости и легкости повторного использования программ.

3) Принципиально важным отличием от предшественников является изначальная ориентация на безопасность кода.

4) Расширенная поддержка событийно-ориентированного программирования.

5)

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

Язык программирования C# является «родным» для создания приложений в среде Microsoft .NET, поскольку наиболее тесно и эффективно интегрирован с ней.

Описание классов

ClassChromosome – класс который создает хромосому.

ClassBackpack – класс рюкзак, который содержит набор необходимых методов для работы с рюкзаком.

ClassGoldberg – класс, который содержит основные методы генетического алгоритма.

ClassProgram – класс для работы с меню.

Описание основных функций

Для полноценной реализации программного средства был разработан ряд методов, которые выполняют заполнение рюкзака, кроссинговер, мутацию и т.д.

Все эти методы описываются в классеclassGoldberg:

1) voidInit() – метод служит для инициализации кроссинговера и мутации.

2) voidInitBackpack() – метод служит для заполнения рюкзака.

3) voidInitPopulation(intlength) – метод служит для инициализации размера популяции.

4) voidWork() – метод работы алгоритма.

5) voidMutation(Chromosomechild) – метод служит для проведения мутации.

6) void NewPopulation(Chromosome childOne, Chromosome childTwo) – методсозданияновойпопуляции.

7) voidPrintBackpack() – метод вывода на экран масс предметов.

8) voidPrintPopulation() – метод вывода на экран популяции.

9) voidCrossover(intone, inttwo) – метод служит для проведения скрещивания двух особей.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

09.03.04.960000.000.ПЗ

Подробное описание классов, полей и методов приведено в ПРИЛОЖЕНИИ В. Фрагменты кода программы приведены в ПРИЛОЖЕНИИ Г. UML диаграмма классов изображена в ПРИЛОЖЕНИИ Б.