ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗБИЕНИЯ МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ

Аннотация

Работа алгоритма разбиения базируется на использовании коллективной эволюцион- ной памяти, под которой подразумевается информация, отражающая историю поиска решения и хранится независимо от индивидуумов. Алгоритм, связанный с эволюционной памятью, стремится к запоминанию и многократному использованию способов достиже- ния лучших результатов. Коллективная эволюционная память алгоритма разбиения со- стоит из некоторого количества статистических индикаторов, отображающих для ка- ждого выполненного варианта число θ его вхождений в состав лучших решений на выпол- ненных генерациях алгоритма и число, δ определяющее насколько полезна реализованная альтернатива при формировании результатов на прошлых генерациях алгоритма. Коллек- тив не имеет централизованного управления, и в связи с этим используется непрямой об- мен информацией. Непрямой обмен состоит в выполнении неких действий, в различное время, при которых происходит изменение некоторых частей эволюционной памяти одним агентом. В дальнейшем происходит использование этой измененной информации другими агентами, в этих частях. Вначале на каждой итерации конструктивным алгоритмом формируется nk решений Qk,. Каждое решение Qk является отображением Fk=V→X, пред- ставляется в виде двудольного подграфа Dk и формируется путем последовательного на- значения элементов в узлы. Формирование каждого решения Qk выполняется множеством агентов A, посредством вероятностного выбора каждым агентом ai узла vj. Процесс на- значения элемента в узел включает две стадии. На первой стадии выбирается агент ai, а на второй стадии − узел vj. При этом должно выполняться ограничение: каждому агенту множества A соответствует один единственный узел множества V. Рассчитывается оценка ξk решения Qk и оценка полезности δk множества альтернатив, реализованных агентами в решении Qk. На втором этапе агенты увеличивают в интегральной россыпи альтернатив R* интегральную полезность множества альтернатив на величину δk.. На третьем этапе осуществляется снижение оценок полезности δk интегральной россыпи альтернатив на величину μ. В работе используется циклический метод формирования ре- шений. В этом случае наращивание оценок интегральной полезности δk множества пози- ций P выполняется после полного формирования множества решений Q на итерации l. Экспериментальные исследования проводились на основе сформированных тестовых при- меров с полученным ранее оптимальным решением. Полученные результаты сравнивались с результатами полученными другими известными алгоритмами разбиения схем на части. Для сравнения был сформирован набор стандартных бенчмарок. Проанализировав получен- ные результаты, можно сделать вывод, что предложенный метод позволяет получать на 4–5 % решения качественнее, чем его аналоги.