Soft Computing

Введение в мягкие вычисления.

1. Нейронные сети;
2. Эволюционные стратегии;
3. Нечеткая логика;
4. Многоагентные системы (интеллект стаи);
5. Различные эвристические алгоритмы поиска решений;
6. Теория хаоса и др.

Программист.

Продуктом деятельности программиста является программа - алгоритм в чистом виде. Не думаю, что найдется кто-то, кто сможет утверждать, что данная профессия неинтеллектуальна, хотя\ldots есть и здесь подводные камни. К примеру, в программе есть кусок кода, решающий уже готовую проблему. Программист берет его, меняет несколько символов (констант) и получает дублированный код, адаптированный к новой предметной области. Речь идет о типичном грехе copy/paste. Не будем здесь рассуждать о недостатках такого подхода - взглянем на это с другой стороны. Новый алгоритм не был рожден. Значит, интеллектуальность такого результата близка к нулю.

Мошенник.

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

Сыщик.

Пожалуй, можно сказать, что профессия сыщика и мошенника составляет синергетическую пару. Чем более интеллектуален мошенник, тем больше интеллекта нужно сыщику, чтобы разоблачить преступника, изобретая ответные нестандартные методы поиска.

Кассир (банк, магазин и т.п.).

В этой профессии изобретение нового алгоритма - зло. Все нужно делать тщательно, аккуратно и одинаково. Ни в коем случае не хочу сказать, что кассиры - неумные люди. Для того чтобы научиться данной работе, интеллект необходим. Зачастую немалый. Но во время самой работы "блок" алгоритмизации необходимо отключать. Поэтому не могу назвать эту профессию интеллектуальной согласно принятому определению.

Водитель.

Сочетание заранее алгоритмизированной деятельности (соблюдение правил дорожного движения, стандартные приёмы управления автомобилем) и постоянный поиск алгоритмов решения возникающих проблем. Это распознавание дорожной ситуации при большом количестве участвующих объектов, движущихся в разных направлениях с разными скоростями, поиск (суб-) оптимального маршрута при движении в незнакомом месте, реагирование на изменившиеся условия движения в уже знакомых местах (ямы, ремонт дороги, новые дорожные знаки). Неудивительно, что эту деятельность еще не автоматизировали до конца, есть только отдельные компоненты, помогающие в решении отдельных задач, например, GPS-навигаторы.

Эволюционные вычисления.

Краткая история.

• Изменчивость - новые особи популяции практически всегда немного (а иногда сильно) отличаются от своих родителей.
• Отбор - естественный или искусственный отбор отсеивают неудачные варианты изменений. Жить остаются только удачные (более приспособленные).
• Наследственность - изменения, произошедшие в одном из поколений, наследуются потомками.

Генетический алгоритм.

• двоичный формат;
• формат с плавающей запятой.

1. Генерация первоначальной случайной популяции.
2. Генерация следующего поколения.
3. Отбраковка худших решений во вновь сгенерированном поколении.
4. Если не достигнут критерий окончания, переходим на шаг 2.
5. Окончание работы. Экземпляр, у которого самое лучшее значение фитнесс-функции, является искомым решением.

• Сортируем родительское поколение в соответствии со значением фитнесс-функции для каждого экземпляра.
• Пока не сгенерировано достаточное количество экземпляров новых поколений:
  1. Отбираем двух родителей.
  2. Объединяем их хромосомы (кроссовер).
  3. Применяем другие генетические операторы.

Схема основного цикла генетического алгоритма.

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

(b) и (c) - применение генетических операторов. Основой ГА являются два оператора: кроссовер, который объединяет решения родителей, и мутация, которая обеспечивает поисковые способности. Кроме этих основных операторов могут также применяться дополнительные операторы, например, инверсия.

Иллюстрация работы одноточечного кроссовера.

Иллюстрация мутации.

Иллюстрация инверсии.

Простой пример реализации ГА.

private static Random _rnd = new Random();
const int GenerationSize = 10000;
const int GenerationNumbers = 200;
constdoubleMutationProbability = 0.2;

public static void Main(string[] args)
{
    // Инициализируем нулевое поколение.
    List<KeyValuePair<int, double>> generation = GenerateRandom();
    SortGeneration(generation);
    // Основной цикл генерации
    for (int genNum = 1; genNum < GenerationNumbers; ++genNum)
    {
        generation = GenerateNewGeneration(generation, true);
        SortGeneration(generation);
        Console.WriteLine("Лучшая особь = " +
        Weight(generation[0].Key));
        Console.WriteLine("Generation " + genNum);
    }
    Console.WriteLine("x = " + GetX(generation[0].Key));
    Console.WriteLine("y = " + GetY(generation[0].Key));
    Console.WriteLine("Genome = {\{}0:X{\}}", generation[0].Key);
    Console.Write("Press any key to continue . . . ");
    Console.ReadKey(true);
}

private static List<KeyValuePair<int, double>> GenerateRandom()
{
    List<KeyValuePair<int, double>> result = new List<KeyValuePair <int,double>>();
    for (int i = 0; i < GenerationSize * 2; ++i)
    {
        int genome = _rnd.Next();
        result.Add(new KeyValuePair(genome,
        Weight(genome)));
    }
    return result;
}

privatestaticvoidSortGeneration(List<KeyValuePair<int,double>>generation)
{
    generation.Sort((x, y) => y.Value.CompareTo(x.Value));
    if (generation.Count > GenerationSize)
        generation.RemoveRange(GenerationSize,
        generation.Count - GenerationSize);
}

private static double GetY(int genome)
{
    int y = genome {\&} 0xffff;
    return y * (1.28 + 1.28) / (0x10000 - 1.0) - 1.28;
}
private static double GetX(int genome)
{
    int x = (genome >> 16) {\&} 0xffff;}=
    return x * (1.28 + 1.28) / (0x10000 - 1.0) - 1.28;
}
private static double Sqr(double x)
{
    return x * x;
}
private static double Weight(int genome)
{
    double x = GetX(genome);
double y = GetY(genome);
    return 100 / (100 * Sqr(Sqr(x) - y) + Sqr(1 - x) + 1);
}

private static List<KeyValuePair<int, double>>
    GenerateNewGeneration(
    List<KeyValuePair<int, double>> parents, bool useElitism)
    {
        List<KeyValuePair<int, double>> result =
        new List<KeyValuePair<int,double>>();
        // Реализация элитизма
        if (useElitism)
            result.Add(parents[0]);
        while (result.Count < GenerationSize * 2)
        {
            // Tурнирный выбор предков}
            int parent1a = _rnd.Next(GenerationSize);
            int parent1b = _rnd.Next(GenerationSize);
            int parent2a = _rnd.Next(GenerationSize);
            int parent2b = _rnd.Next(GenerationSize);
            int parent1 = Math.Min(parent1a, parent1b);
            int parent2 = Math.Min(parent2a, parent2b);
            // Генерация с кроссовером
            int mask = ($\sim \(0 << _rnd.Next(32));
            int child = parents[parent1].Key {\&} mask \(\vert \(
            parents[parent2].Key {\&} \(\sim \(mask;
            // Мутация
            if (_rnd.NextDouble() > MutationProbability)
            child ^= 1 << _rnd.Next(32);
            result.Add(new KeyValuePair<int, double>
            (child, Weight(child)));
        }
        return result;
}

....
Поколение 197
Лучшая особь = 99,9999998156313
Поколение 198
Лучшая особь = 99,9999998156313
Поколение 199
x = 0,999995727473869
y = 0,999995727473869
Геном = E3FFE3FF
Нажмите "Ввод" для выхода . . .

Приведем пример работы генетического алгоритма для подбора строк с целью восстановления надписи "Hello, World!". Для запуска скрипта, щелкните мышкой на надписи.

a

О влиянии генератора случайных чисел на работу ГА.

1. Функция Гривонка (Griewangk’s function). Пусть n − натуральное число, тогда \[ F(x_1,x_2,\ldots,x_n)=1+\sum_{i=1}^n\frac{x_i^2}{4000}-\prod_{i=1}^n\cos\frac{x_i}{\sqrt{i}}, (-6000\le x_i\le 6000,i=1,2,\ldots,n). \] Функция Гривонка близка по виду на функцию Растригина. Она имеет триллион локальных экстремумов. Однако эти локальные экстремумы регулярно распределены по всей поверхности функции. Глобальный минимум, равный 0, достигается в точке \(x_1=x_2=\ldots=x_n=0\). При \(n =10\) существует еще 4 локальных минимума, которые равны \(0,0074\), и достигаются приблизительно в точке \((\pm \pi,\pm \sqrt{2}\pi,0,\ldots,0)\).

   
   Функция Гривонка для случая двух переменных.

2. Функция Розенброка (Rosenbrock's saddle или second function of De Jong). Функция Розенброка входит в набор тестовых функций De Jong и носит второе название De Jong 2. Пусть \(n\) − натуральное число, тогда \[ f(x)=\sum_{i=1}^{n-1}\left(100\left(x_{i+1}-x_i^2\right)^2+\left(x_i-1\right)^2\right). \] Интервал, которому принадлежит переменная: \(−5.12 \lt x_i \lt 5.12, i =1,2,..., n \).

   
   Функция Розенброка для случая двух переменных.

   Данная функция была предложена Ховардом Розенброком в 1960 году. Эта функция имеет крайне пологий изогнутый овраг, который очень усложняет поиск минимума (значения аргументов в точке минимума очевидны: \(\bar{x}_1=\ldots =\bar{x}_n=1\)(при этом \(f(\bar{x})=0\)). Для случая двух переменных функция создает небольшое плато с двумя «крыльями» по обеим сторонам. Точка минимума (1,1) находится на одной стороне плато, в то время как поисковые алгоритмы часто «застревают» на другой стороне. Благодаря сложным для методов поиска особенностям экстремума функция Розенброка часто используется для тестирования сходимости разных оптимиза ционных алгоритмов и для их сравнения.

• генератор Мерсена (стандартный);
• линейный конгруэнтный генератор (ЛКГ);
• генератор Фибоначчи с запаздыванием.

• функция Гривонка – 0;
• функция Розенброка – 0;

Ближе к реальности, или пространственный кроссовер.

public class Explosion
{
    public float X { set; get;}
    public float Y { set; get;}
    public Explosion Clone()
    {
        Explosion copy = new Explosion()
        {
            X = this.X,
            Y = this.Y,
        };
        return copy;
    }
    static Random rnd = new Random();
    public static Explosion GenerateRandom(TaskSpecification spec)
    {
        return new Explosion()
        {
            X = (float)(rnd.NextDouble() * spec.Bound.Width
                + spec.Bound.Left),
            Y = (float)(rnd.NextDouble() * spec.Bound.Height
                + spec.Bound.Top),
        };
    }
}

public class TaskSpecification
{
    public RectangleF Bound {get; set;}
    public int ExplositionsNumber {get; set;}
    public float KillingRadius {get; set;}
    public Bitmap OriginalField {get; set;}
}

Схема пространственного кроссовера.

1. Выбираем в пространстве решаемой задачи произвольную (случайную) точку.
2. У обоих родителей вырезаем одинаковую (по координатам центра и радиусу) окружность (сферу или гиперсферу для пространств с размерностью более 2-х).
3. У одного родителя берем точки, которые лежат внутри окружности, у другого - снаружи.
4. Объединяем взятые точки в одно решение.
5. Корректируем количество точек в потомке - удаляем (случайным образом), если есть лишние, либо добавляем еще не использованные точки родителей.

publicList<Explosion>Explosions = newList<Explosion>();
public double Fitness = Double.MaxValue;

public static Individual GenerateRandom(TaskSpecification spec)
{
    var result = new Individual();
    for (int i = 0; i < spec.ExplositionsNumber; ++i)
       result.Explosions.Add(Explosion.GenerateRandom(spec));
    return result;
}

public void Mutate(TaskSpecification spec)
{
    Explosions[rnd.Next(Explosions.Count)] =
    Explosion.GenerateRandom(spec);
}

public void SpatialCrossoverWith(Individual parent2,
    TaskSpecification spec)
{
    float x0 = (float)(rnd.NextDouble() * spec.Bound.Width
            + spec.Bound.Width);
    float y0 = (float)(rnd.NextDouble() * spec.Bound.Height
            + spec.Bound.Height);
    float radius = (float)(rnd.NextDouble()
            * Math.Max(spec.Bound.Width, spec.Bound.Height));
    List<Explosion> newGenome = new List<Explosion>();
    bool[] used1 = new bool[spec.ExplositionsNumber];
    bool[] used2 = new bool[spec.ExplositionsNumber];
    bool[] deleted = new bool[spec.ExplositionsNumber * 2];
    // Добавляем точки из первого решения
    for (int i = 0; i < spec.ExplositionsNumber; ++i)
    {
        Explosion sp = this.Explosions[i];
        if (radius > Math.Abs(sp.X - x0) + Math.Abs(sp.Y - y0))
        {
            newGenome.Add(sp.Clone());
            used1[i] = true;
        }
    }
    // Добавляем точки из второго решения
    for (int i = 0; i < spec.ExplositionsNumber; ++i)
    {
        Explosion sp = parent2.Explosions[i];
        if (radius <= Math.Abs(sp.X - x0) + Math.Abs(sp.Y - y0))
        {
            newGenome.Add(sp.Clone());
            used2[i] = true;
        }
    }
    // Приводим количество точек нового решения к необходимому
    if (newGenome.Count > spec.ExplositionsNumber)
    {
    // Удаляем лишние точки
    int num = newGenome.Count - spec.ExplositionsNumber;
    for (int i = 0; i < num; ++i)
    {
        int delNum;
        do
        {
            delNum = rnd.Next(newGenome.Count);
        }
        while (deleted[delNum]);
        deleted[delNum] = true;
    }
    List<Explosion> tmpGenome = new
        List<Explosion>(spec.ExplositionsNumber);
    for (int i = 0; i < newGenome.Count; ++i)
        if (!deleted[i])
            tmpGenome.Add(newGenome[i]);
    newGenome = tmpGenome;
    }
    else if (newGenome.Count < spec.ExplositionsNumber)
    {
    // Добавляем недостающие из первого решения
    while (newGenome.Count < spec.ExplositionsNumber)
    {
        int addNum;
        do
        {
            addNum = rnd.Next(spec.ExplositionsNumber);
        }
        while (used1[addNum]);
        used1[addNum] = true;
        newGenome.Add(this.Explosions[addNum]);
    }
}
// Копируем полученное решение в геном первого родителя
Explosions = newGenome;
}

radius>Math.Abs(sp.X - x0) +Math.Abs(sp.Y - y0).

public void Stepping(TaskSpecification spec)
{
    int indexOfChange = rnd.Next(Explosions.Count);
    float shiftX = (float)((rnd.NextDouble() - 0.5) *
    spec.KillingRadius * 0.25);
    float shiftY = (float)((rnd.NextDouble() - 0.5) *
    spec.KillingRadius * 0.25);
    Explosion explosition = Explosions[indexOfChange];
    explosition.X = Limit(explosition.X + shiftX, spec.Bound.Left,
    spec.Bound.Right);
    explosition.Y = Limit(explosition.Y + shiftY, spec.Bound.Top,
    spec.Bound.Bottom);
}
private float Limit(float x, float min, float max)
{
    if (x < min)
        return min;
    if (x > max)
        return max;
return x;
}

private List<Individual> NewGeneration(List<Individual> generation)
{
    var result = new List<Individual>(GenerationSize);
    if (UseElitism)
        result.Add(generation[0].Clone());
    while (result.Count < GenerationSize)
    {
        Individual parent1 = GetTournamentResult(generation);
        Individual newIndividual = parent1.Clone();
        if (rnd.NextDouble() < CrossoverProb)
        {
            Individual parent2 = GetTournamentResult(generation);
            newIndividual.SpatialCrossoverWith(parent2, spec);
        }
        if (rnd.NextDouble() < MutationProb)
            newIndividual.Mutate(spec);
        if (rnd.NextDouble() < SteppingProb)
            newIndividual.Stepping(spec);
        result.Add(newIndividual);
    }
    return result;
}

Исходная область для поражения.

лучший представитель нулевого (случайного) поколения. Качество 3435.	лучший представитель 5-го поколения. Качество 3170.	лучший представитель 20-го поколения. Качество 2688.	лучший представитель 100-го поколения. Качество 2214.	лучший представитель 500-го поколения. Качество 2153.

Результаты применения эволюционного алгоритма.

Генетическое программирование.

Алгоритм вычисления значения функции \((a-15)(b/(a+c))\), представленный в виде дерева.

Алгоритм значения функции \((a-15)(b/(a+c))\), представленный в линейном виде (код какого-то виртуального процессора).

Геном небольшой программы для виртуального процессора, представленный в сетевом (графовом) виде.

Кроссовер для линейного представления генома.

Кроссовер при древовидном представлении генома.

(NOT (NOT X))
(AND \ldots (OR X X))
(+ \ldots (- X X))
(+ X 0)
(* X 1)
(* \ldots (DIV X X))
(MOVE-LEFT MOVE-RIGHT)
(IF (2=1) \ldots X)
(A := A)

To be, or not to be...

classProgram
{
    static void Main(string[] args)
    {
        GPWorld world = new GPWorld();
        for (int g = 0;
        world.Generation[0].Genome != GPWorld.SecretPattern; ++g)
        {
            WriteWorldState(g, world);
            world.Next(true);
        }
        WriteWorldState("last", world);
        Console.WriteLine("The solution found!");
        Console.ReadLine();
    }
    private static void WriteWorldState(object generation, GPWorld
    world)
    {
    Console.WriteLine("Best individual {0}:", generation);
    Console.WriteLine(" Genome=" + world.Generation[0].Genome);
    Console.WriteLine(" Length=" + world.Generation[0].Genome.Length);
    Console.WriteLine(" Fitness=" + world.Generation[0].Fitness);
    Console.WriteLine("----------");
    }
}

public class Individual
{
    public string Genome = "";
    publicdoubleFitness = 0;
}

publicclassGPWorld
{
    privatestaticchar[] _possibleLetters =
    "abcdefghijklmnopqrstuvwxyz' ABCDEFGHIJKLMNOPQRSTUVWXYZ,;.-?
    \(\backslash
    \(r$\backslash \(n".ToCharArray();
    private Random _rnd = new Random();
    private StringBuilder _sb = new StringBuilder();

public const string SecretPattern =
@"To be, or not to be, that is the question;
...

...
And lose the name of action.";
public List Generation;
public const int GenerationSize = 100000;
public const double CrossoverProbability = 0.4;
public const double MutationProbability = 0.2;

publicGPWorld()
{
    Generation = GenerateRandomGeneration();
    SortGeneration(Generation);
}

private void SortGeneration(List<Individual> generation)
{
    generation.Sort((y, x) => x.Fitness.CompareTo(y.Fitness));
}
private List<Individual> GenerateRandomGeneration()
{
    List<Individual> result = new List<Individual>();
    for (int i = 0; i < GenerationSize; ++i)
    {
        int length = _rnd.Next(1, SecretPattern.Length * 2);
        _sb.Length = 0;
        for (int l = 0; l < length; ++l)
        {
            _sb.Append(RandomPossibleChar());
        }
    result.Add(new Individual()
    {
        Genome = _sb.ToString(),
    }
);
result[i].Fitness = CalcFitness(result[i].Genome);
}
return result;
}

private char RandomPossibleChar()
{
    return
    _possibleLetters[_rnd.Next(_possibleLetters.Length)];
}

public double CalcFitness(string genome)
{
    double result = 0;
    int maxLength = Math.Max(SecretPattern.Length, genome.Length);
    int minLength = Math.Min(SecretPattern.Length, genome.Length);
    for (int i = 0; i < maxLength; ++i)
    {
        if (i >= minLength){
            result -= 1;}
        else if (genome[i] != SecretPattern[i]){
            result -= 1;
        else{
            result += 1;
        }
    }
    return result;
}

public void Next(booluseElitism)
{
    List<Individual> newGeneration = new List<Individual>();
    if (use Elitism)
        newGeneration.Add(Generation[0]);
    while (newGeneration.Count<GenerationSize)
    {
// Tурнирный выбор предков из более приспособленной половины
        int parent1a = _rnd.Next(GenerationSize / 2);
        int parent1b = _rnd.Next(GenerationSize / 2);
        int parent2a = _rnd.Next(GenerationSize / 2);
        int parent2b = _rnd.Next(GenerationSize / 2);
        int parent1 = Math.Min(parent1a, parent1b);
        int parent2 = Math.Min(parent2a, parent2b);
string newGenome = (_rnd.NextDouble() < CrossoverProbability)
    Crossover(Generation[parent1].Genome,
    Generation[parent2].Genome) :
    Generation[parent1].Genome;
    if (_rnd.NextDouble() < MutationProbability)
        newGenome = Mutate(newGenome);
    Individual individual = new Individual()
    {
        Genome = newGenome,
    };
    individual.Fitness = CalcFitness(individual.Genome);
    newGeneration.Add(individual);
    }
     SortGeneration(newGeneration);
     Generation = newGeneration;
}

private string Mutate(string genome)
{
// Случайная вставка
    if (_rnd.NextDouble() < 0.33)
    {
        int pos = _rnd.Next(genome.Length + 1);
        _sb.Length = 0;
        for (int i = 0; i < pos; ++i)
            _sb.Append(genome[i]);
        _sb.Append(RandomPossibleChar());
        for (int i=pos; i<genome.Length; ++i)
            _sb.Append(genome[i]);
        genome = _sb.ToString();
    }
    // Случайное удаление
    if (genome.Length > 0 {\&}{\&} _rnd.NextDouble() < 0.33)
    {
        int pos = _rnd.Next(genome.Length);
        genome = genome.Remove(pos, 1);
    }
    // Случайное изменение
    if (genome.Length > 0 {\&}{\&} _rnd.NextDouble() < 0.33)
    {
        int pos = _rnd.Next(genome.Length);
        _sb.Length = 0;
        for (int i = 0; i < genome.Length; ++i)
            if (i != pos)
                _sb.Append(genome[i]);
            else
                _sb.Append(RandomPossibleChar());
            genome = _sb.ToString();
    }
    return genome;
}

private string Crossover(stringgenome1, stringgenome2)
{
    int pos = _rnd.Next(genome1.Length);
    _sb.Length = 0;
    for (int i = 0; i < genome1.Length; ++i)
        if (i > pos)
            _sb.Append(genome1[i]);
        else
            if (i < genome2.Length)
                _sb.Append(genome2[i]);
            else
                _sb.Append(RandomPossibleChar());
    return_sb.ToString();
    }
}

Поколение 0:
Genome=EA-B;-gOcLaRGGhjaQonoAFaHWz
S?QlBBQs;UaoUIpGBUJYLoUeUpd-.eEh?g.XqfYWpoPaLm
...
;u,sW.rAFbkYs
Length=1409
Fitness=-1350
Поколение 500
Genome=TE be, or notGto b?, tpan .' Ghe eBeJtiln;
WhetRer Vpis irblgrBgT tfekqi dxto iuWdIrw
The SliJ?sLaIn Ao
...
ADd losG theonCme of a-tikn.
Length=1442
Fitness=182

Поколение 1000:
Genome=To be, or not to be, that is the qBestion;
Whether 'tis nobler in the mind to sufder
The Slings ann Arrmws of outrageous
...
ADd lose the name of action.
Length=1442
Fitness=1066

Поколение 1426:
Genome=To be, or not to be, that is the question;
Whether 'tis nobler in the mind to suffer
The Slings and Arrows of outrageous Fortune
...
And lose the name of action.
Length=1442
Fitness=1442

Интеллект стаи.

Животные (человек как высшее проявление) - уже понятно, что за все очень сложное поведение отвечает система относительно простых (но все еще не до конца изученных) элементов, нейронов.

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

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

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

Процесс оптимизации пути при переносе найденной пищи (А) в муравейник (В).

1. Создаем муравьев.
2. Муравьи ищут решения.
3. Обновление уровня феромона.

1. Начальные точки, куда помещаются муравьи, зависят от ограничений задачи. В простейших случаях, мы можем их всех поместить в одну точку, либо случайно распределить по площади лабиринта. На этом же этапе каждое ребро лабиринта помечается небольшим положительным числом, характеризующим запах феромона. Это нужно для того, чтобы на следующем шаге у нас не было нулевых вероятностей.
2. Определяем вероятность перехода из вершины i в вершину j по следующей формуле: \[ P_{i,j} (t) = \frac{\tau _{i,j} (t)^\alpha \left( {d_{i,j} } \right)^{ - \beta }}{\sum\nolimits_{j \in connected\mbox{ nodes}} {\tau _{i,j} (t)^\alpha \left( {d_{i,j} } \right)^{ - \beta }} }. \] Здесь \(\tau _{i,j} (t)\) - уровень феромона, \(d_{i,j}\) - эвристическое расстояние, \(\alpha ,\beta \) - константы.
   Если \(\alpha =0\), то наиболее вероятен выбор ближайшего соседа, и алгоритм становится "жадным".
   В случае \(\beta =0\), наиболее вероятен выбор только на основе уровня феромона, что приводит к застреванию на уже "протоптанных" путях.
   Как правило, используется некоторое компромиссное значение этих величин, подбираемое экспериментально для каждой задачи.
3. Обновление уровня феромона производится следующим образом: \[ \tau _{i,j} (t + 1) = (1 - \rho )\tau _{i,j} (t) + \sum\nolimits_{k \in usededge(i,j)} {\frac{Q}{L_k (t)}.} \]

Задача коммивояжера и муравьиный алгоритм.

public class AntOptimizer
{
    class Town
    {
        public double X {set; get; }
        public double Y {set; get; }
    }
    class RouletteSector
    {
        public double Start = 0;
        publicintTown = -1;
    }

Town[] _towns = null;
Random _rnd = new Random();
double[,] _distanses = null;
double[,] _scents = null;
double GetScent(int town1, int town2)
{
return _scents[Math.Min(town1, town2), Math.Max(town1, town2)];
}
void AddScent(int town1, int town2, double scent)
{
_scents[Math.Min(town1, town2), Math.Max(town1, town2)] +=scent;
}

publicAntBestWay = null;
publicdoubleBestWayLength = Double.MaxValue;
publicintStepCount = 0;

public AntOptimizer(int townNumber)
{
    // Проверяем параметры.
    if (townNumber < 3)
    throw new ArgumentOutOfRangeException("townNumber", townNumber,
    "'townNumber' should be more then 2");
    // Инициализируем города случайными координатами.
    _towns = newTown[townNumber];
    for (int t = 0; t < townNumber; ++t)
    {
        _towns[t] = new Town()
        {
            X = _rnd.NextDouble(),
            Y = _rnd.NextDouble()
        };
    }
    // Заполняем таблицу расстояний между городами.
    _distanses = new double[townNumber,townNumber];
    for (int t1 = 0; t1 < townNumber; ++t1)
    {
        Town town1 = _towns[t1];
        for (int t2 = 0; t2 < townNumber; ++t2)
        {
            Town town2 = _towns[t2];
            _distanses[t1, t2] = Math.Sqrt(Sqr(town1.X -
            town2.X) + Sqr(town1.Y - town2.Y));
        }
    }
    // Инициализируем таблицу запахов.
    _scents = new double[townNumber, townNumber];
    for (int i = 0; i < townNumber; ++i)
        for (int j = i + 1; j < townNumber; ++j)
            _scents[i, j] = 1.0;
    }

public void Step(double alpha, double beta, double q)
{
    StepCount++;
    int townNumber = _towns.Length;
// По очереди пускаем муравьев. Проверяем, какой маршрут наилучший.
    for (int a = 0; a < townNumber; ++a)
    {
        Ant ant = new Ant(this, a);
        double wayLength = ant.Move(alpha, beta, q);
        if (wayLength < BestWayLength)
        {
            BestWay = ant;
            BestWayLength = wayLength;
        }
    }
    // Испаряем ферромоны
    for (int i = 0; i < townNumber; ++i)
    for (int j = i + 1; j < townNumber; ++j)
        _scents[i, j] = _scents[i, j] * 0.9;
}

public class Ant
{
private AntOptimizer _owner;
private int _townNumber = -1;
private int _startTown;
private Dictionary<int, int> _pathHash = new Dictionary<int,int>();
public List<int> Path = new List<int>();

public Ant(AntOptimizer owner, int startTown)
{
    _owner = owner;
    _startTown = startTown;
    _townNumber = _owner._towns.Length;
}

public double Move(double alpha, double beta, double q)
{
    double pathLength = 0;
    Path.Add(_startTown);
    _pathHash.Add(_startTown, _startTown);
    int currentTown = _startTown;
    for (int i = 1; i < _townNumber; ++i)
    {
        currentTown = FindNextTown(currentTown, alpha, beta);
        Path.Add(currentTown);
        _pathHash.Add(currentTown, currentTown);
    }
    Path.Add(_startTown);
    for (int i = 0; i < _townNumber; ++i)
        pathLength += _owner._distanses[Path[i], Path[i + 1]];
        for (int i = 0; i < _townNumber; ++i)
        _owner.AddScent(Path[i], Path[i + 1], q / pathLength);
    return pathLength;
}

private int FindNextTown(int currentTown, double alpha, double beta)
{
    // Заполняем "рулетку" с неравными секторами
    List<RouletteSector> rouletteSectors = new List<RouletteSector>();
    double sum = 0;
    for (int i = 0; i < _townNumber; ++i)
    {
        if (!_pathHash.ContainsKey(i))
        {
            rouletteSectors.Add(
            new RouletteSector()
            {
                Start = sum,
                Town = i,
                });
        sum +=
Math.Pow(_owner.GetScent(currentTown, i), alpha) /
Math.Pow(_owner._distanses[currentTown, i], beta);
}
}
// Выбираем на "рулетке" случайный сектор бинарным поиском
    double val = _owner._rnd.NextDouble() * sum;
    int a = 0; int b = rouletteSectors.Count;
    while (b - a > 1)
        {
            int c = (a + b) / 2;
            if (rouletteSectors[c].Start < val)
             a = c;
            else
                b = c;
        }
    return rouletteSectors[a].Town;
    }
}

Скриншоты решения задачи коммивояжера.

В заключение приведем несколько интересных примеров использования генетического программирования.

• Sato et al. (2002) использовал генетические алгоритмы для создания концертного зала с оптимальными акустическими свойствами, максимального качества звука как для аудитории, так и для дирижера и музыкантов.
• Obayashi et al. (2000) использовал генетический алгоритм для разработки формы крыла для сверхзвукового самолета.
• Keane и Brown (1996) использовали ГА, чтобы разработать новую конструкцию для несущей фермы или стрелы, которые могут быть собраны на орбите и использованы для спутников, космических станций и других проектов аэрокосмического строительства. Результат - скрученная, органично выглядящая структура, превосходящая по прочности и устойчивости к вибрации конструкции на основе стандартного дизайна.

  
  Генетически оптимизированная трехмерная ферма с улучшенной частотной характеристикой.

• Gibbs (1996 , Lockheed Martin) использовал генетический алгоритм для разработки серии маневров с целью перевода космического корабля с одной орбиты на другую. Разработанное решение позволило провести маневр на 10% быстрее, чем решение, предложеное специалистами по той же проблеме.
• Altshuler и Linden (1997) использовали генетический алгоритм для разработки проволочных антенн с заранее заданными свойствами.

  

• Самбридж и Галлахер (1993) использовали генетический алгоритм для обнаружения гипоцентров землетрясений на основе сейсмологических данных.
• Giro, Cyrillo и Galvão (2002) использовали генетические алгоритмы для проектирования электропроводящих углеродных полимеров.

Задачи для самостоятельной работы.

Вопрос-ответ.