Scipy Дифференциальная эволюция с целыми числами

Я пытаюсь запустить оптимизацию с помощью scipy.optimize. Differential_evolution. Код требует границ для каждой переменной в x. Но мне нужно решение, в котором части x должны быть целыми числами, а другие могут свободно варьироваться в виде чисел с плавающей запятой. Соответствующая часть моего кода выглядит так

    bounds = [(0,3),(0,3),(0,3),???,???]
    result = differential_evolution(func, bounds)

Что мне заменить ???, чтобы заставить эти переменные быть целыми в заданном диапазоне?


python scipy mathematical-optimization differential-evolution
person arriana    schedule 18.02.2016    source источник
comment
Вы не можете. На самом деле ни один из решателей в scipy.optimize не поддерживает такое ограничение. pyevolve и DEAP — это две другие библиотеки Python для создания генетических алгоритмов, которые предлагают контроль над вашей функцией мутации, так что вы можете ограничить некоторые или все элементы в ваших векторах решений целыми числами. В зависимости от характера вашей проблемы вы также можете взглянуть на библиотеки целочисленного программирования, такие как cvxpy или PuLP.   -  person ali_m    schedule 19.02.2016
comment
Хорошо спасибо. Тогда я пойду разбираться с DEAP.   -  person arriana    schedule 19.02.2016
comment
Удачи! Вероятно, вам следует подумать о том, можно ли выразить вашу проблему оптимизации в форме, которую можно решить с помощью существующего Решатели ILP или MILP. Имитация отжига может быть еще одним вариантом, который стоит изучить. Мне трудно давать какие-либо конкретные рекомендации, ничего не зная о характере проблемы, которую вы пытаетесь решить.   -  person ali_m    schedule 19.02.2016

Ответы (2)


arrow_upward
3
arrow_downward

Как отмечено в комментариях, прямой поддержки «целочисленного ограничения» нет.

Однако вы можете минимизировать измененную целевую функцию, например:

def func1(x):
    return func(x) + K * (x[3] - round(x[3]))**2

и это заставит x[3] приблизиться к целочисленному значению (к сожалению, вам придется настроить параметр K).

Альтернативой является округление (некоторых) параметров с действительным знаком перед оценкой целевой функции:

def func1(x):
    z = x;
    z[3] = round(z[3])
    return func(z)

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

person manlio    schedule 27.05.2016
comment
Это два интересных подхода. Первый, кажется, дает единственное решение, но за счет дополнительного параметра ($K$). Есть ли какие-либо рекомендации относительно конкретного выбора одного из двух для данных типичных типов задач? Например, в случае двоичной переменной? А как насчет объединения двух подходов? - person Unis; 15.02.2018
comment
@Unis Я пробовал второй для некоторых задач планирования, и он работал довольно хорошо. Не знаю, есть ли рекомендации... - person manlio; 15.02.2018

arrow_upward
1
arrow_downward

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

Из исходного кода scipy видно, что их DE основан на Storn, R и Price, K, Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, 1997.

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

Есть несколько статей, которые вносят изменения в алгоритм, чтобы он мог обрабатывать целые числа. У меня не было времени просмотреть все варианты, но, возможно, эта статья могла бы помочь.

Усовершенствованный алгоритм дифференциальной эволюции для задач программирования смешанных целых чисел

person Jon    schedule 03.10.2017