Функция кроссовера для генетических

Question

Я пишу генератор таблицы времени в java, используя подходы AI, чтобы удовлетворить жесткие ограничения и помочь найти оптимальное решение. До сих пор я реализовал и итеративную конструкцию (наиболее ограниченную первую эвристику) и Simulated Annealing, и я нахожусь в процессе реализации генетического алгоритма.

Некоторой информация о проблеме, и как я представляю его тогда: У меня есть набор событий, комнаты, особенности (что события требуют и номер удовлетворяет), студенты и слоты Проблемы заключаются в присвоении каждого событиечрезвычайном слот и комнату, так что ни один студент не должен присутствовать на двух мероприятиях в одном слоте, все назначенные номера отвечают необходимым требованиям.

У меня есть функция оценки, которая для каждого набора, если присвоения оценивает нарушения мягкого ограничения, таким образом, точка должна минимизировать это.

Как я реализую GA, я начинаю с совокупности, сгенерированной итеративной конструкцией (которая может оставить события неназначенными), а затем выполните обычные шаги: оценивайте, выбирайте, перекрещивайте, мутируйте и сохраняйте лучшее. Промыть и повторить.

Моя проблема заключается в том, что мое решение, похоже, слишком мало улучшается. Независимо от того, что я делаю, популяции склонны к случайной физической форме и застряли там. Обратите внимание, что эта пригодность всегда отличается, но тем не менее появляется нижний предел.

Я подозреваю, что проблема в моей функции кроссовера, а вот логика позади него:

Два задания выбираются случайным образом пересекаться. Позволяет называть их назначениями A и B. Для всех событий B выполните следующую процедуру (случайные события заказа B выбраны случайными):

Получите соответствующее событие в A и сравните задание. Возможны 3 разных ситуации.

• Если только один из них не назначается, и если можно повторить другое назначение на ребенке, выбирает это назначение.
• Если они оба назначены, но только один из них не создает конфликтов
  при назначении ребенку этого выбранного.
• Если они оба назначены, и ни один из них не создает конфликт, то из их выбирают случайным образом.

В любом другом случае событие остается неназначенным.

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

Что касается мутации, я использую соседнюю функцию моего SA, чтобы дать мне другое задание на основе дочерних элементов, а затем заменить этого ребенка.

Так что снова. С этой установкой, начальная популяция 100, GA работает и всегда стремится стабилизироваться при некотором случайном (высоком) значении пригодности. Может ли кто-нибудь дать мне указатель относительно того, что я могу сделать неправильно?

Благодаря

Edit: форматирование и очистить некоторые вещи

Answer 1

Я думаю, GA имеет смысл только в случае, если часть решения (часть вектора) имеет значение как самостоятельные части решения, так что функция кроссовера объединяет действительные части решения между двумя векторами решения. Подобно тому, как определенная часть последовательности ДНК контролирует или влияет на конкретный аспект индивидуального окраса глаз, например, один ген. Однако в этой задаче разные части вектора решения влияют друг на друга, делая кроссовер почти бессмысленным. Это приводит (моя догадка) в алгоритме, сходившемся на одном решении довольно быстро, с различными кроссоверами и мутациями, имеющими только негативное влияние на фитнес.

Я не верю, что это правильный инструмент для решения этой проблемы.

Answer 2

Если вы могли бы предоставить оригинальное заявление о проблеме, я смогу дать вам лучшее решение. Вот мой ответ на данный момент.

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

Линейные программы позволяют пользователям минимизировать или максимизировать некоторые цели, моделируемые целевой функцией (функция оценки). Целевая функция определяется суммой отдельных решений (или переменных решения) и значения или вклада в целевую функцию. Линейные программы позволяют десятичным значениям принимать переменные решения, но целые программы заставляют переменные решения быть целыми.

Итак, каковы ваши решения? Ваши решения - назначить учащихся слотам. И эти слоты имеют функции, которые требуют события, и комнаты удовлетворяют.

В вашем случае вы хотите увеличить число учащихся, назначенных слоту.

У вас также есть ограничения. В вашем случае студент может посещать не более одного мероприятия.

На следующем веб-сайте приведено хорошее руководство по моделированию целочисленных программ.

http://people.brunel.ac.uk/~mastjjb/jeb/or/moreip.html

Для конкретной реализации Java, используйте ссылку ниже.

http://javailp.sourceforge.net/

SolverFactory factory = new SolverFactoryLpSolve(); // use lp_solve 
factory.setParameter(Solver.VERBOSE, 0); 
factory.setParameter(Solver.TIMEOUT, 100); // set timeout to 100 seconds 

/** 
* Constructing a Problem: 
* Maximize: 143x+60y 
* Subject to: 
* 120x+210y <= 15000 
* 110x+30y <= 4000 
* x+y <= 75 
* 
* With x,y being integers 
* 
*/ 
Problem problem = new Problem(); 

Linear linear = new Linear(); 
linear.add(143, "x"); 
linear.add(60, "y"); 

problem.setObjective(linear, OptType.MAX); 

linear = new Linear(); 
linear.add(120, "x"); 
linear.add(210, "y"); 

problem.add(linear, "<=", 15000); 

linear = new Linear(); 
linear.add(110, "x"); 
linear.add(30, "y"); 

problem.add(linear, "<=", 4000); 

linear = new Linear(); 
linear.add(1, "x"); 
linear.add(1, "y"); 

problem.add(linear, "<=", 75); 

problem.setVarType("x", Integer.class); 
problem.setVarType("y", Integer.class); 

Solver solver = factory.get(); // you should use this solver only once for one problem 
Result result = solver.solve(problem); 

System.out.println(result); 

/** 
* Extend the problem with x <= 16 and solve it again 
*/ 
problem.setVarUpperBound("x", 16); 

solver = factory.get(); 
result = solver.solve(problem); 

System.out.println(result); 
// Results in the following output: 

// Objective: 6266.0 {y=52, x=22} 
// Objective: 5828.0 {y=59, x=16} 

Answer 3

Я хотел бы начать с измерения того, что происходит непосредственно. Например, какая часть присвоений подпадает под ваш «какой-либо другой случай», и поэтому ничего не делает?

Кроме того, хотя мы не можем действительно рассказать по предоставленной информации, похоже, что ни одно из ваших действий не может сделать «обмен», что может быть проблемой. Если график жестко ограничен, то, как только вы найдете что-то выполнимое, вполне вероятно, что вы не сможете просто переместить класс из комнаты A в комнату B, поскольку комната B будет использоваться. Вам нужно будет рассмотреть способы перемещения класса от А до В вместе с перемещением класса от В до А.

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

Наконец, возможно, что и ваши другие операторы также являются проблемой. Если ваши операторы выбора и замены слишком агрессивны, вы можете очень быстро сблизиться с чем-то, что только немного лучше, чем там, где вы начали. Как только вы сходитесь, очень сложно только для мутаций выгнать вас в продуктивный поиск.

Answer 4

Я думаю, что нет ничего плохого в GA для этой проблемы, некоторые люди просто ненавидят генетические алгоритмы независимо от того, что.

Вот что я хотел бы проверить:

Прежде всего отметим, что ваш GA стабилизируется на случайном «Высокий» фитнес значение, но это не очень хорошая вещь? Соответствует ли «высокий» фитнес хорошему или плохому в вашем случае? Возможно, вы предпочитаете «высокий» фитнес в одной части своего кода и «низкий» фитнес в другой, что приводит к кажущемуся случайному результату.

Я думаю, вы хотите быть немного более осторожным в отношении логики вашей кроссоверной операции. В основном существует множество ситуаций для всех трех случаев, когда любой из этих вариантов не будет приводить к увеличению пригодности для всех перекрестных лиц, но вы все еще используете «ресурс» (назначение, которое потенциально может быть использовано для другого класс/ученик/и т. д.) Я понимаю, что GA традиционно будет выполнять задания через кроссовер, которые вызывают худшее поведение, но вы все равно выполняете немного вычисления на фазе кроссовера, почему бы не выбрать тот, который действительно улучшит физическую форму, или, может быть, дон Крест вообще?

Дополнительный комментарий к рассмотрению: хотя ваш итеративный подход к построению довольно интересен, это может привести к чрезмерно сложному представлению Джин, которое может вызвать проблемы с вашим кроссовером. Можно ли моделировать отдельное индивидуальное решение как массив (или 2D-массив) бит или целых чисел? Даже если массив окажется очень длинным, возможно, стоит использовать более простую процедуру кроссовера. Я рекомендую googling «ga gene presentation time tabling», вы можете найти подход, который вам больше нравится, и его можно более легко масштабировать для многих людей (100 - это довольно небольшой размер популяции для GA, но я понимаю, что вы все еще тестируете, а также сколько поколения?).

Наконец-то я не уверен, на каком языке вы работаете, но если это Java, и вам НЕ требуется кодировать GA вручную, я бы порекомендовал взглянуть на ECJ. Может быть, даже если вам придется вручную подбирать код, это может помочь вам развить ваше представительство или разводящий трубопровод.

Answer 5

Попавшие в ГА может сделать любой из ряда стандартных ошибок:

• В общем, когда делать кроссовер, убедитесь, что у ребенка есть какой-то шанс унаследовать то, что сделал родителя или родителей победителя (с) в первую очередь. Другими словами, выберите представление генома, в котором фрагменты гена гена имеют значимые сопоставления с описанием проблемы. Общей ошибкой является кодирование всего как битвектора, а затем, в кроссовере, разбиение битвектора в случайных местах, разделение того, что представляет битвектор, и тем самым уничтожение вещи, которая сделала отдельное плавание на вершину хорошим кандидатом. Вектор (ограниченных) целых чисел, вероятно, будет лучшим выбором, где целые числа могут быть заменены мутацией, но не кроссовером. Не сохраняя что-то (не обязательно на 100%, но это должен быть какой-то аспект) того, что сделало родителей победителями, значит, вы делаете случайный поиск, который будет лучше, чем линейный.

• В общем, используйте гораздо меньшую мутацию, чем вы думаете. Мутация существует в основном для сохранения разнообразия в населении.Если ваша первоначальная популяция не содержит ничего с дробным преимуществом, то ваше население слишком мало для этой проблемы, и высокий уровень мутации, в общем, не поможет.

• В этом конкретном случае функция кроссовера слишком сложна. Никогда не ставьте ограничения, направленные на то, чтобы все решения были включены в кроссовер. Вместо этого функция кроссовера должна быть свободной для создания недействительных решений, и задача целевой функции - несколько (а не полностью) штрафует недействительные решения. Если ваша ГА работает, то окончательные ответы не будут содержать никаких недействительных присвоений, при условии, что 100% действительных назначений вообще возможны. Настаивание на достоверности кроссовера не позволяет действительным решениям принимать ярлыки через недействительные решения для других и более эффективных решений.

Я бы рекомендовал всем, кто думает, что они написали неэффективные GA провести следующий тест: Запуск ГА несколько раз, и обратите внимание на количество поколений потребовалось, чтобы достичь приемлемого результата. Затем замените шаг выбора победителя и функцию цели (независимо от того, что вы используете - турнир, рейтинг и т. Д.) Со случайным выбором, и запустите его снова. Если вы все еще сходитесь примерно с той же скоростью, что и с реальной функцией оценщика/цели, у вас фактически не было функционирующей GA. Многие люди, которые говорят, что GA не работают, допустили ошибку в своем коде, что означает, что GA сходится так же медленно, как и случайный поиск, которого достаточно, чтобы отвлечь кого-либо от этой техники.