Программный комплекс для изучения методов глобальной оптимизации «GlOpt» — страница 5

  • Просмотров 706
  • Скачиваний 5
  • Размер файла 364
    Кб

задачу о расстановке N шахматных ферзей на доске размером N*N. Ферзи должны быть расставлены так, чтобы ни один из них не бил другого. Это означает, что ни на одной вертикали, горизонтали или диагонали не могут находиться два ферзя одновременно. Иными словами, функция коллизий должна принимать минимальное значение. Пример решения задачи для размерности N = 8 показан на рисунке 2. Рис. 2 Данная задача в течение многих лет решалась

известными математиками, такими как Гаусс, однако оптимальное решение найдено не было. Задача может решаться непосредственно - алгоритмом полного перебора с возвратом, однако это не позволяет рассматривать данную задачу при достаточно больших N. На обычном персональном компьютере за разумное время может быть получен результат лишь для N менее 15. В то же время с помощью метода имитации отжига задача может достаточно эффективно

решаться для значительно большей размерности, однако при достаточно больших N решение может содержать коллизии. 4.2. Задача об «Умном муравье» Действие происходит на поверхности тора размером 32x32 клетки. В некоторых клетках находится еда. Муравей начинает движение из клетки, помеченной «Start». За ход муравей может выполнить следующие действия: повернуть налево; повернуть направо; сделать шаг вперед и, если в новой клетке есть еда,

съесть ее; ничего не делать. Игра длится 200 ходов. Цель игры - создать муравья «с минимальным числом состояний», который за минимальное число ходов съест как можно больше яблок. Рис. 3 Визуализатор особи в задаче об умном муравье комплекса GLOpt 5. Структура программного комплекса GLOpt Важнейшим критерием при создании программного комплекса являлось удобство и легкость его расширения на максимальное количество задач оптимизации.

Реализация этой задачи потребовала разработки специальной программной структуры, которая бы полностью соответствовала предъявляемым требованиям к масштабируемости, а также была бы довольно простой для понимания, позволяя желающим внедрять и анализировать методы оптимизации, не вошедшие в рамки данной работы. Основные классы фреймворка GLOpt, реализованного на языке С# под платформой Microsoft.NET, представлены на рисунке 4.

Управляющий класс Brain ответственен за загрузку основных сущностей программного комплекса: Problem, Optimizer, ISearchOperator, а также осуществляет контроль над текущими процессами. Сама же задача глобальной оптимизации полностью описывается абстрактными классами Problem, Algorithm, Individual, SearchOperator, от которых в свою очередь наследуются классы, реализующие конкретные задачи, например, задачу «умного муравья» или же метод имитации отжига. 5.2 Класс