Как инициализировать хромосомы в эволюционном алгоритме для решения LP/ILP или общей COS для реальных переменных?

Question

Я работаю над инфраструктурой Java для задач оптимизации. До сих пор я реализовал lp_solve и GLPK и поэтому могу обрабатывать линейные задачи (ЛП) и целочисленные линейные задачи (ИЛП). Теперь я хочу предоставить возможность использования эволюционных алгоритмов в качестве решателя, чтобы иметь возможность обрабатывать проблемы с нелинейными ограничениями или нелинейной целевой функцией. В общем, для решения проблем оптимизации ограничений (COS). Я нашел Apache commons genetic package для генетических алгоритмов и начал внедрять генетический алгоритм.

Хромосома в моем алгоритме представляет собой решение проблемы оптимизации, то есть оно состоит из карты Variable -> Number. Теперь, в первом населении, я хотел бы случайно создать решение и начать развиваться оттуда. Следовательно, мне нужно найти случайные значения для переменных. У меня есть доступ к нижнему и верхнему границам переменной и является ли ее доменом Целые значения - это Реальные. Поэтому я инициирую переменные следующим образом:

//Create a Random Number generator 
Random generator = new Random(); 

//Create a new Map to store the variables and their assigned values 
Map<String,Number> newRepresentation = new HashMap<String,Number>(); 

//Iterate over all variables from the problem 
for (Entry<String,Variable> entry : problem.getVariables().entrySet()) { 
    Variable variable = entry.getValue(); 
    Number uB = variable.getUpperBound(); 
    Number lB = variable.getLowerBound(); 
    //Create a random value for this variable 
    Number randomValue = (generator.nextDouble() * (uB.doubleValue() - lB.doubleValue())) + lB.doubleValue(); 
    //If the variable has Integers as its domain, make the random value an Integer 
    if (variable.getType() == OptVarType.INTEGER) randomValue = randomValue.intValue(); 
    newRepresentation.put(variable.getName(), randomValue); 
} 

Это должно дать мне карту newRepresentation с заданием всех переменных в случайные числа. Однако, если переменная не ограничена, т. Е. Нижняя граница равна 0, а верхняя граница равна Integer.MAX_VALUE, я никогда не получаю значения, близкие к нижней границе. Например, у меня есть проблема

max 3x+4y 
s.t. 
x+2y <= 14 
3x-y >= 0 
x-y <= 2 
x in {0,...,2147483647} 
y in {0,...,2147483647} 

Тогда оптимальное решение является x=6, y=4. Но переменные инициализируются мой EA, как:

A new Population has been initiated: {y=1430866067, x=1616622921} 
A new Population has been initiated: {y=1483081480, x=1389387196} 
A new Population has been initiated: {y=242558338, x=376547119} 
A new Population has been initiated: {y=1861689859, x=959676986} 
... 

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

Вопрос: Как я могу изменить начало хромосом, так что значения равномерно распределены по всему пространству поиска?

Answer 1

Во-первых, я подумал, сохраняются ли ваши целые значения равномерно после вашей трансформации.

Пример:

Вы хотите создать целое число от 5 до 10. Таким образом, вы создаете равномерно распределены дважды в этом интервале (который прекрасно работает с кодом) и вероятность его пребывания в [5,5.5) равна вероятности того, что он находится в [5.5.6], в [6.6.5], ..., [9.5, 10]. Теперь, чтобы преобразовать его в целое число, вы заполняете значение, сопоставляя два из интервалов, которые я описал, каждому возможному целочисленному значению. Поэтому мне это кажется прекрасным.

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

1. Генератор случайных чисел неисправен. (что маловероятно, если вы используете стандартный JDK)
2. Вы выполняете слишком мало испытаний, чтобы получить низкие начальные значения - интервал довольно большой.

EDIT: Я просмотрел документацию класса Number. Преобразование в целое число можно использовать как округление ИЛИ округление. Если он использует округление, случайные целочисленные значения больше не равномерно распределены, поэтому вы должны явно ввести двойное значение.