Мне всегда интересно было, почему работают генетические алгоритмы. Когда работал программистом, однажды решал многомерную задачу о рюкзаке — у нас есть порядка ста предметов, у них есть несколько характеристик, и их надо разбить на группы, так что каждая группа удовлетворяет неравенствам. Для каждой характеристики, её сумма (или другая функция, близкая к линейной) по элементам группы лежит в заданных пределах.
Ну и какая-то там целевая функция была (нужно как можно больше объектов использовать), близкая к линейной. Удивительным образом, получалось что генетические алгоритмы (мы интерпретируем раскладку элементов по группам как последовательность генов организма, дальше можно скрещивать разные организмы.) работают лучше всего. Ну и это такой известный факт.
Сейчас я несколько раз наткнулся в обсуждениях на topological data analysis, и про это вспомнил.
Появилась идея такого вычислительного проекта — надо взять “типичную” задачу о таком мультирюкзаке и попробовать топологически понять что происходит. Топологически это выглядит следующим образом —- мы рассматриваем все возможные разбиения множества объектов на группы. Это такое топологическое пространство, где расстояние мерится по метрике Хэмминга или что-то вроде того. Потом мы выбрасываем из этого пространства все точки где целевая функция “не близка” к максимуму.
Полученное пространство X уже имеет дырки и топологически нетривиально. Теперь на этом пространстве действуют два оператора — условно фенотипический и генетический. Фенотипический оператор получает на вход любую точку исходного пространства и локальными улучшениями (поменять местами объекты в группах, попробовать заменить объект из группы на один или два неиспользованных и тд) приводит её к точке пространства X, локальному максимуму.
Генетический оператор действует так, Он берёт две точки из X и производит скрещивание (например, берёт первую половину разбиения из первой точки, вторую половину из второй точки, потом удаляет все дважды встретившиеся объекты). Таким образом, на пространстве X есть умножение — берём две точки, применяем генетический оператор, в потом фенотипический к результату.
Если мы верим в то, что генетические алгоритмы всегда работают, то, начав со случайных точек в X, многократное применение такого умножения должно быть типа эргодичным, и мы сколь угодно близко подберёмся к глобальному максимуму. Получается две задачи — топологическая (при каких условиях на операторы получится эргодичная динамика), и вычислительная — надо запускать много экспериментов и вообще смотреть что получается. Опять же, там есть building block hypothesis, что все хорошие решения собраны из небольшого числа средней длины генов, это тоже можно попробовать интерпретировать топологически.
Не знаете ли Вы кого-нибудь, кому это может быть интересно, потому что один я этим заниматься (и программировать всё это) вряд ли буду?
Ну и какая-то там целевая функция была (нужно как можно больше объектов использовать), близкая к линейной. Удивительным образом, получалось что генетические алгоритмы (мы интерпретируем раскладку элементов по группам как последовательность генов организма, дальше можно скрещивать разные организмы.) работают лучше всего. Ну и это такой известный факт.
Сейчас я несколько раз наткнулся в обсуждениях на topological data analysis, и про это вспомнил.
Появилась идея такого вычислительного проекта — надо взять “типичную” задачу о таком мультирюкзаке и попробовать топологически понять что происходит. Топологически это выглядит следующим образом —- мы рассматриваем все возможные разбиения множества объектов на группы. Это такое топологическое пространство, где расстояние мерится по метрике Хэмминга или что-то вроде того. Потом мы выбрасываем из этого пространства все точки где целевая функция “не близка” к максимуму.
Полученное пространство X уже имеет дырки и топологически нетривиально. Теперь на этом пространстве действуют два оператора — условно фенотипический и генетический. Фенотипический оператор получает на вход любую точку исходного пространства и локальными улучшениями (поменять местами объекты в группах, попробовать заменить объект из группы на один или два неиспользованных и тд) приводит её к точке пространства X, локальному максимуму.
Генетический оператор действует так, Он берёт две точки из X и производит скрещивание (например, берёт первую половину разбиения из первой точки, вторую половину из второй точки, потом удаляет все дважды встретившиеся объекты). Таким образом, на пространстве X есть умножение — берём две точки, применяем генетический оператор, в потом фенотипический к результату.
Если мы верим в то, что генетические алгоритмы всегда работают, то, начав со случайных точек в X, многократное применение такого умножения должно быть типа эргодичным, и мы сколь угодно близко подберёмся к глобальному максимуму. Получается две задачи — топологическая (при каких условиях на операторы получится эргодичная динамика), и вычислительная — надо запускать много экспериментов и вообще смотреть что получается. Опять же, там есть building block hypothesis, что все хорошие решения собраны из небольшого числа средней длины генов, это тоже можно попробовать интерпретировать топологически.
Не знаете ли Вы кого-нибудь, кому это может быть интересно, потому что один я этим заниматься (и программировать всё это) вряд ли буду?
I was always interested in why genetic algorithms work. When I worked as a programmer, I once solved a multidimensional task about a backpack - we have about a hundred items, they have several characteristics, and they need to be divided into groups, so that each group satisfies inequalities. For each characteristic, its sum (or another function that is close to linear) for the elements of the group lies within the specified limits.
Well, there was some kind of objective function (you need to use as many objects as possible), close to linear. Surprisingly, it turned out that genetic algorithms (we interpret the layout of elements into groups as a sequence of genes in an organism, then you can cross different organisms) work best. Well, this is such a well-known fact.
Now I stumbled several times in discussions on topological data analysis, and remembered that.
The idea of such a computational project emerged - it is necessary to take the “typical” problem of such a multirudder and try topologically to understand what is happening. Topologically, it looks like this — we consider all possible partitions of a set of objects into groups. This is such a topological space where the distance is measured according to the Hamming metric or something like that. Then we throw out from this space all the points where the objective function is “not close” to the maximum.
The resulting space X already has holes and is topologically nontrivial. Now there are two operators in this space - conditionally phenotypic and genetic. The phenotypic operator receives as input any point of the source space and local improvements (swap objects in groups, try to replace an object from the group with one or two unused, etc.) leads it to the point of space X, the local maximum.
The genetic operator acts like this. It takes two points from X and makes a crossing (for example, takes the first half of the split from the first point, the second half from the second point, then removes all twice-encountered objects). Thus, on the space X there is a multiplication - we take two points, apply the genetic operator, then phenotypic to the result.
If we believe that genetic algorithms always work, then, starting from random points in X, the repeated use of such multiplication should be ergodic, and we can get as close as possible to the global maximum. It turns out two tasks - topological (under what conditions the operators will get ergodic dynamics), and computational - you need to run a lot of experiments and generally see what happens. Again, there is a building block hypothesis, that all good solutions are collected from a small number of medium-length genes; this can also be interpreted topologically.
Do you know anyone who might be interested in it, because I’m not going to do this alone (and program it all)?
Well, there was some kind of objective function (you need to use as many objects as possible), close to linear. Surprisingly, it turned out that genetic algorithms (we interpret the layout of elements into groups as a sequence of genes in an organism, then you can cross different organisms) work best. Well, this is such a well-known fact.
Now I stumbled several times in discussions on topological data analysis, and remembered that.
The idea of such a computational project emerged - it is necessary to take the “typical” problem of such a multirudder and try topologically to understand what is happening. Topologically, it looks like this — we consider all possible partitions of a set of objects into groups. This is such a topological space where the distance is measured according to the Hamming metric or something like that. Then we throw out from this space all the points where the objective function is “not close” to the maximum.
The resulting space X already has holes and is topologically nontrivial. Now there are two operators in this space - conditionally phenotypic and genetic. The phenotypic operator receives as input any point of the source space and local improvements (swap objects in groups, try to replace an object from the group with one or two unused, etc.) leads it to the point of space X, the local maximum.
The genetic operator acts like this. It takes two points from X and makes a crossing (for example, takes the first half of the split from the first point, the second half from the second point, then removes all twice-encountered objects). Thus, on the space X there is a multiplication - we take two points, apply the genetic operator, then phenotypic to the result.
If we believe that genetic algorithms always work, then, starting from random points in X, the repeated use of such multiplication should be ergodic, and we can get as close as possible to the global maximum. It turns out two tasks - topological (under what conditions the operators will get ergodic dynamics), and computational - you need to run a lot of experiments and generally see what happens. Again, there is a building block hypothesis, that all good solutions are collected from a small number of medium-length genes; this can also be interpreted topologically.
Do you know anyone who might be interested in it, because I’m not going to do this alone (and program it all)?
У записи 9 лайков,
1 репостов.
1 репостов.
Эту запись оставил(а) на своей стене Никита Калинин
