public struct SetOfBox //структура описывающая груз
{
public double b_lenght; //длина
public double b_width; //ширина
public double b_height; //высота
public bool isPacked; //упакован?
public SetOfBox(double s1, double s2, double s3, bool s4)
{
this.b_lenght = s1; //длина
this.b_width = s2; //ширина
this.b_height = s3; //высота
this.isPacked = s4;
}
};
Генетический алгоритм [C#]
Добрый день.
Мне необходимо решить задачу двумерной упаковки прямоугольников с использованием генетического алгоритма. До этого с генетическими алгоритмами не сталкивался, поэтому прошу помочь.
Прямоугольники описываю структурой:
SetOfBox[][] setBoxes; - в этом массиве массивов храню множества грузов отсортированных по высоте.
После прочтения статьи на вики, попробовал создать начальную популяцию:
Возникли следующие вопросы:
1. Если размер популяции не кратен k, то остаются не упакованные ящики
2. Хотя бы идея у меня правильная?
Хотелось бы услышать ваши советы и рекомендации:)
Мне необходимо решить задачу двумерной упаковки прямоугольников с использованием генетического алгоритма. До этого с генетическими алгоритмами не сталкивался, поэтому прошу помочь.
Прямоугольники описываю структурой:
Код:
SetOfBox[][] setBoxes; - в этом массиве массивов храню множества грузов отсортированных по высоте.
После прочтения статьи на вики, попробовал создать начальную популяцию:
Код:
// особь - набор ящиков
// n - общее количество ящиков
// k - количество генов у особи (количество ящиков в наборе)
// n/k - размер популяции
public int k = 4;
public SetOfBox[][] population; // [особь][набор генов]
public Random r = new Random();
public void setPopulation(SetOfBox[][] setBoxes)
{
//берём первое подмножество
for (int i = 0; i < setBoxes.Length; i++)
{
int n = setBoxes.Length / k; //размер популяции
/* популяция состоит из n особей, каждая особь имеет набор из 4 генов*/
population = new SetOfBox[n][];
// для каждой особи заполним генотип
for (int j = 0; j < n; j++)
{
population[j] = new SetOfBox[k]; //у каждой особи набор из 4 генов
int index = 0; //индекс ящика в наборе setBoxes
for (int t = 0; t < k; t++)
{
for (; ; )
{
index = (int)r.Next(0, (int)setBoxes.Length); //случайным образом выбираем ящик (ген)
if (!setBoxes[index].isPacked) //если ящик не использовали
{
population[j][t] = setBoxes[index]; //выбираем его
setBoxes[index].isPacked = true; //помечаем как упакованный
break;
}
}
}
}
richTextBox1.Text += "Подмножество: " + (i+1) + " Размер популяции: " + n + " каждая особь имеет набор из " + k + " генов \n";
}
for (int i = 0; i < population.Length; i++)
{
richTextBox1.Text += "Тип " + i + ": \n";
for (int j = 0; j < population.Length; j++)
{
richTextBox1.Text += "Длина=" + population[j].b_lenght + " Ширина=" + population[j].b_width + " Высота=" + population[j].b_height + "\n";
}
}
}
// n - общее количество ящиков
// k - количество генов у особи (количество ящиков в наборе)
// n/k - размер популяции
public int k = 4;
public SetOfBox[][] population; // [особь][набор генов]
public Random r = new Random();
public void setPopulation(SetOfBox[][] setBoxes)
{
//берём первое подмножество
for (int i = 0; i < setBoxes.Length; i++)
{
int n = setBoxes.Length / k; //размер популяции
/* популяция состоит из n особей, каждая особь имеет набор из 4 генов*/
population = new SetOfBox[n][];
// для каждой особи заполним генотип
for (int j = 0; j < n; j++)
{
population[j] = new SetOfBox[k]; //у каждой особи набор из 4 генов
int index = 0; //индекс ящика в наборе setBoxes
for (int t = 0; t < k; t++)
{
for (; ; )
{
index = (int)r.Next(0, (int)setBoxes.Length); //случайным образом выбираем ящик (ген)
if (!setBoxes[index].isPacked) //если ящик не использовали
{
population[j][t] = setBoxes[index]; //выбираем его
setBoxes[index].isPacked = true; //помечаем как упакованный
break;
}
}
}
}
richTextBox1.Text += "Подмножество: " + (i+1) + " Размер популяции: " + n + " каждая особь имеет набор из " + k + " генов \n";
}
for (int i = 0; i < population.Length; i++)
{
richTextBox1.Text += "Тип " + i + ": \n";
for (int j = 0; j < population.Length; j++)
{
richTextBox1.Text += "Длина=" + population[j].b_lenght + " Ширина=" + population[j].b_width + " Высота=" + population[j].b_height + "\n";
}
}
}
Возникли следующие вопросы:
1. Если размер популяции не кратен k, то остаются не упакованные ящики
2. Хотя бы идея у меня правильная?
Хотелось бы услышать ваши советы и рекомендации:)
Идея такая. ген индимидума хранит информацию о (x,y - базовой точки фигуры и угол поворота вокруг этой базовой точки (если нужно)
1 Генерируешь популяцию(случайным образом расставляешь прямоугольные фигуры на плоскости)
2. Кросовер(берешь два индивидуума и в цикле с рандомной вероятностью производи обмен информации о местоположении у и-той детали.
3. Рассчет фитнес функции(можешь считать из суммарной площади наложения фигур друг на друга + площадь выхода за пределы заданного полотна)
3 Отсев плохих результатов( тут алгоритмов много, нужно попробовать разные и выбрать наилучший)
1 Генерируешь популяцию(случайным образом расставляешь прямоугольные фигуры на плоскости)
2. Кросовер(берешь два индивидуума и в цикле с рандомной вероятностью производи обмен информации о местоположении у и-той детали.
3. Рассчет фитнес функции(можешь считать из суммарной площади наложения фигур друг на друга + площадь выхода за пределы заданного полотна)
3 Отсев плохих результатов( тут алгоритмов много, нужно попробовать разные и выбрать наилучший)
Цитата: Rad87
Идея такая. ген индимидума хранит информацию о (x,y - базовой точки фигуры и угол поворота вокруг этой базовой точки (если нужно)
1 Генерируешь популяцию(случайным образом расставляешь прямоугольные фигуры на плоскости)
2. Кросовер(берешь два индивидуума и в цикле с рандомной вероятностью производи обмен информации о местоположении у и-той детали.
3. Рассчет фитнес функции(можешь считать из суммарной площади наложения фигур друг на друга + площадь выхода за пределы заданного полотна)
3 Отсев плохих результатов( тут алгоритмов много, нужно попробовать разные и выбрать наилучший)
1 Генерируешь популяцию(случайным образом расставляешь прямоугольные фигуры на плоскости)
2. Кросовер(берешь два индивидуума и в цикле с рандомной вероятностью производи обмен информации о местоположении у и-той детали.
3. Рассчет фитнес функции(можешь считать из суммарной площади наложения фигур друг на друга + площадь выхода за пределы заданного полотна)
3 Отсев плохих результатов( тут алгоритмов много, нужно попробовать разные и выбрать наилучший)
спасибо:)
А как формировать популяцию, как я делал (несколько особей, с определенным количеством генов) или у каждой особи, будет количество генов равное общему количеству деталей, но у этих деталей разные х,у: пусть имеется 8 типов коробок (a,b,c...) я делал так:
особь1 имеет гены (a,b,c,d)
особь2 - (e,f,g,h).
Или же нужно делать:
особь 1 - (a,b,c,d,e,f,g,h)
особь 2 - (a',b',c',d',e',f',g',h')
объясните пожалуйста...
Цитата: Енот_в_Засаде
Мне необходимо решить задачу двумерной упаковки прямоугольников с использованием генетического алгоритма.
Что значит двумерная упаковка? Это двумерная задача о рюкзаке?
А каким боком тут "генетика"?
Цитата: hardcase
Что значит двумерная упаковка? Это двумерная задача о рюкзаке?
А каким боком тут "генетика"?
А каким боком тут "генетика"?
она самая, я реализовал простой "жадный" алгоритм, с поставленной задачей он справлялся на ура, но руководитель где-то от кого-то слышал, что генетический алгоритм справится с задачей лучше...
Цитата: Енот_в_Засаде
она самая, я реализовал простой "жадный" алгоритм, с поставленной задачей он справлялся на ура, но руководитель где-то от кого-то слышал, что генетический алгоритм справится с задачей лучше...
В теории он может справиться лучше, но за более длительное время и вообще не факт что добьется необходимой плотности размещения. На практике, если есть алгоритм заточенный под задачу, то нужно его применять. Генетический алгоритм используется в тех случаях когда сложно реализовать необходимую эвристику.
в моем понимании. особь это - конкретное размещение деталей. таким образом Гены я бы представил в следующем виде (x1, y1,a1, x2,y2,a2) (где описывается положение двух фигур особи и их угол поворота)
Спасибо, вы мне очень помогли
Почитай книгу М. Тим Джонс, Программирование искусственного интеллекта в приложениях., раздел про генетические алгоритмы. Там приведен код, да и сам алгоритм достаточно хорошо описан для начинающих.
Если возникнут вопросы, то пиши, помогу как смогу.
Алсо, если я правильно понимаю задачу, то необходимо использовать предопределенные ящики и как гены использовать вовсе не длину/ширину, а положение в ящике по осям х и у (кстати, пишите о двумерной сортировки, а используете в классе еще и высоту, нипанятна). Так почему вы оптимизируете размер ящиков, а не их положение? Оптимизация придет к тому, что размер ящиков уменьшится до минимального. (Помоему, кстати, там вообще ничего оптимизироваться не будет, так как вы просто переставили их по счету, сакральный смысл этого?)
Если возникнут вопросы, то пиши, помогу как смогу.
Алсо, если я правильно понимаю задачу, то необходимо использовать предопределенные ящики и как гены использовать вовсе не длину/ширину, а положение в ящике по осям х и у (кстати, пишите о двумерной сортировки, а используете в классе еще и высоту, нипанятна). Так почему вы оптимизируете размер ящиков, а не их положение? Оптимизация придет к тому, что размер ящиков уменьшится до минимального. (Помоему, кстати, там вообще ничего оптимизироваться не будет, так как вы просто переставили их по счету, сакральный смысл этого?)
Цитата: hivewarrior
Почитай книгу М. Тим Джонс, Программирование искусственного интеллекта в приложениях., раздел про генетические алгоритмы. Там приведен код, да и сам алгоритм достаточно хорошо описан для начинающих.
Если возникнут вопросы, то пиши, помогу как смогу.
Если возникнут вопросы, то пиши, помогу как смогу.
Спасибо:)
Цитата: hivewarrior
кстати, пишите о двумерной сортировки, а используете в классе еще и высоту, нипанятна
Просто, я в дальнейшем собираюсь делать трёхмерную ортогональную упаковку, по алгоритму описанному Псиолой, вот для этого мне высота и пригодиться
Цитата: hivewarrior
Так почему вы оптимизируете размер ящиков, а не их положение? Оптимизация придет к тому, что размер ящиков уменьшится до минимального.
размер ящиков мы не оптимизируем, а пытаемся оптимизировать их размещение на листе заданного размера. т.е. каждая особь - является вариантом упаковки, и из этих вариантов выбираем наиболее подходящий.
P.S. на данный момент я отказался от варианта с ген. алгоритмом, для данной задачи вполне хватило "жадного" алгоритма, а с генетикой очень много времени уходило на проверку перекрытий ящиками друг друга.
P.S.S - большое спасибо всем откликнувшимся, узнал много полезного:)
Мне надо сделать прямоугольный раскрой на основе ГА.
посоветуйте статьи, пожалуйста.
посоветуйте статьи, пожалуйста.
Благодарствую )
А вы можете сказать, чем упаковка отличается от раскроя?
В статье, при упаковке, ещё место остаётся рядом с прямоугольниками...
В статье, при упаковке, ещё место остаётся рядом с прямоугольниками...
Цитата: maxflint
В статье, при упаковке, ещё место остаётся рядом с прямоугольниками...
там рассматривается алгоритм уплотнения, как раз чтоб этих промежутков не оставалось (по возможности). Да и к тому же никто не мешает вам немного переделать этот алгоритм чтобы он удовлетворял вашим требованиям.
Цитата: maxflint
А вы можете сказать, чем упаковка отличается от раскроя?
Задача упаковки заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими.
Задача о раскрое - задача на оптимальное и комплексное распределение сырья или заготовок с наименьшими отходами производства, решаемая методами линейного или целочисленного программирования.
Ну и если сравнивать, то, наверное, раскрой и двумерную упаковку (bin packing), я думаю это практически одно и тоже (конечно если речь идет раскрое упаковке предметов прямоугольной формы а не о фигурном раскрое). И там и там, нужно уместить как можно больше предметов (т.е. разместить их как можно плотнее ) и свести отходы к минимуму.
Спасибо, думаю за неделю реализую