Evolutionary Programming

"Началось это так: В начале была создана Вселенная. Это у многих вызвало крайнее раздражение, и в основном рассматривалось как плохой ход. Многие народы верят, что она была создана каким-нибудь божеством, хотя, к примеру, джадравартиды с Вильтводля VI верят в то, что на самом деле всю Вселенную вычихнуло существо по имени Большой Зеленый Арклохват. Джатравартиды живут в постоянном страхе перед тем, что они называют Пришествием Большого Белого Платка. Это маленькие голубые создания, и у каждого из них пятьдесят рук, так что они -- единственный народ во всей Вселенной, который изобрел дезодорант раньше колеса. Культ Большого Зеленого Арклохвата, однако, не получил большого распространения за пределами системы Вильтводля IV, и поэтому, а также потому, что Вселенная как была, так и остается полна загадок, поиск ответа не прекращается. Например, раса сверхразумных всеразмерных созданий построила себе однажды гигантский суперкомпьютер под названием Глубокомысленный, чтобы он раз и навсегда вычислить Ответ на Главный вопрос Жизни, Вселенной и всего Прочего. Семь с половиной миллионов лет Глубокомысленный считал и рассчитывал, и, наконец, объявил, что нашел ответ: "Сорок два", -- и в результате пришлось строить еще один компьютер, еще больше, чтобы выяснить, какой же вопрос нужно задавать к этому ответу."

Дуглас Адамс. Ресторан на краю Вселенной

Итак я начну тут писать идеи для эволюционного программирования. Буду писать много, не красиво, сбивчиво, прыгая от одного к другому. Такой подход даст возможность развивать идеи для реализации. Я буду описывать что я понимаю под тем, чего хочу достичь и с помощью чего. Параллельно, когда буду видеть, что какие-то идеи будут действующими буду их реализовывать.

Хочу заметить, что то, что я буду делать не будет именно тем, что подразумевает под эволюционным программированием научное сообщество. Так как повторение скорее всего приведёт к заведомо известному конечному результату. Я буду пытаться решить задачу с помощью своих логических выводов от малого к большему. 

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

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

Для начала реализую матрицу. Выполнять буду в среде, где мне удобно на данный момент. Язык bash, консоль. Сделаю матрицу, размер матрицы изначально должен быть регулируемым и 10х10 в начале вполне хватит.

Создаем файл matrix.sh

Итак, для начала bash не поддерживает многомерные массивы. Придется держать все в одномерном и писать логику переноса двумерного представления в одномерный массив данных.

#!/bin/bash

MAX_X=10

MAX_Y=10

LENGTH=$(( $MAX_X * $MAX_Y ))

echo $LENGTH

Для начала заполним его случайной средой как одномерный массив. Массив в таком случае должен содержать среду и в случайных местах клетки с типом "еда"

Но для начала создадим "Землю":

 

ENUM_MATRIX_LAND=0

filling(){

local i

for (( i=1; i <= "$LENGTH"; i++ )); do

matrix[$i]="$ENUM_MATRIX_LAND"

done 

}

  

Теперь нам нужен генератор случайных чисел, не будем же мы вручную наполнять наш дивный мир:

get_random(){

  local -r probability="$1"

  local random

  random=$((1 + RANDOM % probability))

  echo "$random"

}

На входе в него мы имеем параметр probability, который отвечает за диапазон получаемого числа от единицы

Теперь добавим надстройку, возвращающую true или false, в зависимости от входящей вероятности. Будем проверять равен ли random единице и в зависимости от диапазона random сможем регулировать вероятность.

FALSE=0

TRUE=1

get_probability(){

  local -r probability="$1"

  local random

  random="$(get_random $probability)"

  if [ "$random" = "1" ]; then

    echo $TRUE

  else

    echo $FALSE

  fi

}

 

Создадим еду

ENUM_MATRIX_FOOD=1

и добавим ее возможность появления

FOOD_PROBABILITY=3

Это означает возможность появления 1 из 3

Сделаем общую функцию, которая на входе будет получать тип из enum для заполнения и вероятность его возникновения.

filling_type(){

local -r type="$1"

local -r probability="$2" local out

local i

for (( i=1; i <= "$LENGTH"; i++ )); do

  out="$(get_probability $probability)"

  if [ "$out" = $TRUE ]; then

  matrix[$i]="$type"

fi

done

}

Вызов для заполнения едой будет таким:

filling_type "$ENUM_MATRIX_FOOD" "$FOOD_PROBABILITY"

Мы уже получили "мир", но не видим его. Давайте сделаем визуализацию. Создадим функцию drawing_matrix, которая будет выводить мир. Вывод сделаем сначала максимально простым, потом будем эту функцию усложнять.

drawing_matrix(){ 

local i

  for (( i=1; i <= "$LENGTH"; i++ )); do

    echo -n "${matrix[$i]}"

  done

}

 Давайте посмотрим что мы получили:

./matrix.sh

0000110100000000100110000100110000001000010110000000010100000111011001111110000000000000000010001000

Вот он наш мир, полный чудес и загадок!

Теперь надо бы сохранить наш мир, чтобы мир реальный его случайно не уничтожил

git clone https://vilkovsky@bitbucket.org/vilkovsky/evolutionary_programming.git
git add .
git commit -m "1"
git push

И сразу сделаем визуализацию в двумерном представлении.

drawing_matrix(){

  local i

  local x=1

  for (( i=1; i <= "$LENGTH"; i++ )); do

    echo -n "${matrix[$i]} "

    x=$((x+1))

    if [ "$x" -gt "$MAX_X" ]; then

      echo

      x=1

    fi

  done

}

 

./matrix.sh

1 0 0 1 0 0 0 0 0 1 

0 0 1 1 0 1 0 1 0 0 

0 0 0 0 0 0 1 1 0 0 

0 1 0 1 0 1 0 1 0 0 

0 0 1 0 0 1 1 0 0 1 

1 1 0 0 1 0 0 0 0 0 

0 0 1 0 1 0 1 0 0 0 

1 0 0 1 0 0 1 0 0 0 

1 0 1 0 1 0 0 0 0 1 

0 0 0 0 1 0 0 1 0 1 

Так выглядит красота!

Вынесем код, отвечающий за визуализацию в отдельную библиотеку drawing.lib

в нее перенесем функцию drawing_matrix, а в начале нашего кода подключим эту библиотеку:

source drawing.lib

Сделаем рамки мира, дабы видеть где все должно происходить.

FIELD_BORDER_LEFT="|"

FIELD_BORDER_TOP="-"

drawing_border_top_bottom(){

  local x

  echo -n "  "

  for (( x=1; x <= "$MAX_X"; x++ )); do

    echo -n "$FIELD_BORDER_TOP "

  done

  echo

}

drawing_matrix(){

  local i

  local x=1

  drawing_border_top_bottom

  for (( i=1; i <= "$LENGTH"; i++ )); do

    if [ "$x" = "1" ]; then

      echo -n "$FIELD_BORDER_LEFT "

    fi

    echo -n "${matrix[$i]} "

    x=$((x+1))

    if [ "$x" -gt "$MAX_X" ]; then

      echo "$FIELD_BORDER_LEFT"

      x=1

    fi

  done

  drawing_border_top_bottom

}

  - - - - - - - - - - 

| 0 1 0 0 1 1 1 1 0 0 |

| 0 1 1 0 0 0 0 0 0 1 |

| 0 0 0 0 0 0 0 0 0 0 |

| 1 0 1 0 0 1 0 0 0 0 |

| 0 1 0 0 0 0 1 0 0 1 |

| 1 1 1 0 1 1 0 1 0 1 |

| 0 0 1 0 0 1 1 0 0 0 |

| 0 1 0 1 0 0 1 0 0 0 |

| 1 0 0 0 0 0 0 1 1 1 |

| 0 0 0 1 1 0 1 1 1 0 |

  - - - - - - - - - - 

Теперь надо сделать вывод ассоциативным, чтобы вывод полей можно было менять. 

declare -A DRAW_ARR

DRAW_ARR["$ENUM_MATRIX_LAND"]=" "

DRAW_ARR["$ENUM_MATRIX_FOOD"]="#"

и сам вывод

echo -n "${matrix[$i]} "

меняем на 

echo -n "${DRAW_ARR[${matrix[$i]}]} "

Теперь вывод получился таким:

  - - - - - - - - - - 

| #   # #   # #       |

|           #   #   # |

| #     # #           |

| #   # # #   # #     |

| # #   #         #   |

|       # #         # |

| #     #   #       # |

|     # # #   #     # |

| #       #           |

| # #       # # #     |

  - - - - - - - - - - 

Уже вижу как эти бескрайние просторы заселяются первыми простейшими.

Пришла пора создать нашу первую сущность. Создадим для нее отдельную библиотеку entity.lib

и подключим ее в matrix.sh:

source entity.lib

И тут я понял, как мне не будет хватать конструкторов, наследования, объктов с++... Но пока не отвлекаемся от проложенного курса. Тем более у меня есть несколько идей по реализации объектов, но об этом позже. Я уже вижу, как можно усложнить код, сделать все хитро-запутанным, но торопиться не будем. 

 в entity.lib прописываем единственные нужные на данный момент характеристики:

ENTITY1_X=5 

ENTITY1_Y=6

в matrix.sh добавляем существо в enum

ENUM_ENTITY=2

а в drawing.lib добавляем вид этого кошмарного существа:

DRAW_ARR["$ENUM_ENTITY"]="Q"

А ведь у него уже есть хвост!

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

drawing_matrix(){

  local i

  local x=1

  local y

  drawing_border_top_bottom

  for (( i=1; i <= "$LENGTH"; i++ )); do

    y=$((1+$((i/MAX_X))))

    if [ "$x" = "1" ]; then

      echo -n "$FIELD_BORDER_LEFT "

    fi

    if [ "$x" = "$ENTITY1_X" ] && [ "$y" = "$ENTITY1_Y"  ]; then

      echo -n "${DRAW_ARR["$ENUM_ENTITY"]}"

    else

      echo -n "${DRAW_ARR[${matrix[$i]}]}"

    fi

    echo -n " "

    x=$((x+1))

    if [ "$x" -gt "$MAX_X" ]; then

      echo "$FIELD_BORDER_LEFT"

      x=1

    fi

  done

  drawing_border_top_bottom

}

  - - - - - - - - - - 

|   # #         #     |

|   #             #   |

| # # #           #   |

|   # # # #           |

|                 #   |

| # #     Q         # |

| # # #       # #   # |

|   # #   #   # #     |

|   #   # # #   # #   |

|     #       #     # |

  - - - - - - - - - - 

Вот оно сидит и ничего не делает.

Добавим время. Для этого поместим нашу отрисовку в бесконечный цикл:

TIME_INTERVAL=0.1

while true; do

  clear

  drawing_matrix

  sleep "$TIME_INTERVAL"

done

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

drawing_border_top_bottom(){

  local x

  local output

  output="  "

  for (( x=1; x <= "$MAX_X"; x++ )); do

    output+="$FIELD_BORDER_TOP "

  done

  output+="\n"                                                                                  

  echo "$output"                                                                                

}                                                                                               

                                                                                                

drawing_matrix(){                                                                               

  local i                                                                                       

  local x=1                                                                                     

  local y

  local output

  output=$(drawing_border_top_bottom)

  for (( i=1; i <= "$LENGTH"; i++ )); do

    y=$((1+$((i/MAX_X))))

    if [ "$x" = "1" ]; then

      output+="$FIELD_BORDER_LEFT "

    fi

    if [ "$x" = "$ENTITY1_X" ] && [ "$y" = "$ENTITY1_Y"  ]; then

      output+="${DRAW_ARR["$ENUM_ENTITY"]}"

    else

      output+="${DRAW_ARR[${matrix[$i]}]}"

    fi

    output+=" "

    x=$((x+1))

    if [ "$x" -gt "$MAX_X" ]; then

      output+="$FIELD_BORDER_LEFT\n"

      x=1

    fi

  done

  output+=$(drawing_border_top_bottom)

  echo -e "$output"

}

Теперь весь расчет идет в переменную output и только в конце мы делаем ее вывод. Не сказал бы что доволен результатом. Мы убрали моменты, когда можно было увидеть курсор в момент перерисовки, но мерцание осталось. Темная сторона C# зовет меня...

Но есть еще идея. Давайте сделаем минимальной дистанцию от очистки к отрисовки. Правим функцию вывода:

while true; do

  output="$(clear; drawing_matrix)"

  echo "$output"

  sleep "$TIME_INTERVAL"

done

Что ж, мерцания нет. Еще поживем в мире баша.

Отрисовывается настолько хорошо, что уже не понятно, а не зависло ли все. Добавим счетчик на экран. 

Добавляем переменную TIME_COUNTER

TIME_COUNTER=0

и в цикл

while true; do

  output="$(clear; drawing_matrix)"

  echo "$output"

  TIME_COUNTER="$((TIME_COUNTER+1))"

  sleep "$TIME_INTERVAL"

done

В drawing.lib добавляем 

TIME_COUNTER_TEXT="Counter:"

drawing_counter(){

  local text

  text="$TIME_COUNTER_TEXT $TIME_COUNTER"

  echo "$text"

}

В функцию drawing_matrix добавляем вывод счетчика:

drawing_matrix(){

  local i

  local x=1

  local y

  local output

  output=$(drawing_border_top_bottom)

  output+="   $(drawing_counter)"

  output+="\n"

  for (( i=1; i <= "$LENGTH"; i++ )); do

    y=$((1+$((i/MAX_X))))

    if [ "$x" = "1" ]; then

      output+="$FIELD_BORDER_LEFT "

    fi

    if [ "$x" = "$ENTITY1_X" ] && [ "$y" = "$ENTITY1_Y"  ]; then

      output+="${DRAW_ARR["$ENUM_ENTITY"]}"

    else

      output+="${DRAW_ARR[${matrix[$i]}]}"

    fi

    output+=" "

    x=$((x+1))

    if [ "$x" -gt "$MAX_X" ]; then

      output+="$FIELD_BORDER_LEFT\n"

      x=1

    fi

  done

  output+=$(drawing_border_top_bottom)

  echo -e "$output"

}

А из функции drawing_border_top_bottom убираем строку output+="\n" - Не зачем в дочерних функциях управлять переносами.

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

drawing_interface(){

  local output

  output="$(drawing_counter)"

  output+="\n"

  output+="Entity X: $ENTITY1_X Y: $ENTITY1_Y\n"

  echo "$output"

}

и вызываем ее в drawing_matrix

output+="$(drawing_interface)"

И тут нашлась бага. При ENTITY1_X=10 отображение скачет на другую строку. В drawing_matrix не верно рассчитывается y. y=$((1+$((i/MAX_X)))). Поправил на вот так y=$((1+$((((i-1))/MAX_X)))). Возможно можно было бы и лучше, но не время останавливаться на таких мелочах, когда на кону жизнь цивилизации.

Идем дальше. Научим сущность ходить. Заодно добавим проверки, чтобы существо не могло выскочить из мира. Добавляем в entity.lib:

check_position(){

  if [ "$ENTITY1_X" -gt "$MAX_X" ]; then

    ENTITY1_X="$MAX_X"

  elif [ "$ENTITY1_X" -lt "$MIN_X" ]; then

    ENTITY1_X="$MIN_X"

  fi

  if [ "$ENTITY1_Y" -gt "$MAX_Y" ]; then

    ENTITY1_Y="$MAX_Y"

  elif [ "$ENTITY1_Y" -lt "$MIN_Y" ]; then

    ENTITY1_Y="$MIN_Y"

  fi

}

go_left(){

  ENTITY1_X="$((ENTITY1_X+1))"

  check_position

}

go_right(){

  ENTITY1_X="$((ENTITY1_X-1))"

  check_position

}

go_top(){

  ENTITY1_Y="$((ENTITY1_Y-1))"

  check_position

}

go_bottom(){

  ENTITY1_Y="$((ENTITY1_Y+1))"

  check_position

}

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

Создал библиотеку ai.lib

В ней добавил такие функции

processor(){

}

get_pleasure(){

}

get_senses(){

}

get_memory(){

}

get_act(){                                                                                         

                                                                                                   

}      

Каждый ход будет вызывать функция processor, а в ней поочередно будет вызываться сначала функция удовольствий, потом чувств, потом памяти и действий. Напишем код хаотичного движения. Но сначала вынесем функции get_random и get_probability в functions.lib

Для хаотичного движения добавляем в entity.lib:

go_chaotic(){

  local rand

  rand="$(get_random 4)"

  case "$rand" in

    1)

      go_left

    ;;

    2)

      go_right

    ;;

    3)

      go_top

    ;;

    4)

      go_bottom

    ;;

  esac

}

В ai.lib:

processor(){

  get_act

}

get_act(){

  go_chaotic

}

И в наш бесконечный цикл перед выводом добавляем вызов функции processor

Теперь нужно переделать движение, так как оно должно возвращать действие.

check_position(){

  local -r x="$1"

  local -r y="$2"

  local trigger

  trigger=$TRUE

  if [ "$x" -gt "$MAX_X" ]; then

    trigger="$FALSE"

  elif [ "$x" -lt "$MIN_X" ]; then

    trigger="$FALSE"

  fi

  if [ "$y" -gt "$MAX_Y" ]; then

    trigger="$FALSE"

  elif [ "$y" -lt "$MIN_Y" ]; then

    trigger="$FALSE"

  fi

  echo "$trigger"

}

go_left(){

  local x

  x="$((ENTITY1_X+1))"

  if [ "$(check_position "$x" "$ENTITY1_Y")" = "$TRUE" ]; then

    ENTITY1_X="$x"

    return "$MEMORY_GO_LEFT"

  else

    return "$MEMORY_GO_NEVER"

  fi

}

go_right(){

  local x

  x="$((ENTITY1_X-1))"

  if [ "$(check_position "$x" "$ENTITY1_Y")" = "$TRUE" ]; then

    ENTITY1_X="$x"

    return "$MEMORY_GO_RIGHT"

  else

    return "$MEMORY_GO_NEVER"

  fi

}

go_top(){

  local y

  y="$((ENTITY1_Y-1))"

  if [ "$(check_position "$ENTITY1_X" "$y")" = "$TRUE" ]; then

    ENTITY1_Y="$y"

    return "$MEMORY_GO_TOP"

  else

    return "$MEMORY_GO_NEVER"

  fi

}

go_bottom(){

  local y

  y="$((ENTITY1_Y+1))"

  if [ "$(check_position "$ENTITY1_X" "$y")" = "$TRUE" ]; then

    ENTITY1_Y="$y"

    return "$MEMORY_GO_BOTTOM"

  else

    return "$MEMORY_GO_NEVER"

  fi

}

go_chaotic(){

  local rand

  local status

  rand="$(get_random 4)"

  case "$rand" in

    1)

      go_left; status="$?"

    ;;

    2)

      go_right; status="$?"

    ;;

    3)

      go_top; status="$?"

    ;;

    4)

      go_bottom; status="$?"

    ;;

  esac

  return "$status"

}

и в ai.lib добавляем переменные

MEMORY_GO_NEVER=1

MEMORY_GO_LEFT=2

MEMORY_GO_RIGHT=3

MEMORY_GO_TOP=4

MEMORY_GO_BOTTOM=5

и меняем функции

processor(){

  local status

  local mem

  get_act; status="$?"

  mem="$status"

  set_memory "$mem"

}

set_memory(){

  local -r mem="$1"

  ENTITY_MEMORY+=($mem)

}

get_act(){

  local status

  go_chaotic; status="$?"

  return "$status"

}

Теперь у нас есть память существа, в которую записываются действия. Правда оно еще не в состоянии оценить их, чем и нужно заняться

Добавляем параметр энергии

ENTITY_ENERGY=100

action_entity(){

  processor

  consumption_energy

}

consumption_energy(){

  ENTITY_ENERGY="$((ENTITY_ENERGY-1))"

}

И меняем вызов в цикле с processor на action_entity, ведь у существа не только мозги будут. Вот уже и энергия горит.

Добавляем функцию взаимодействия с окружающей средой

interaction_with_the_environment(){

  local z

  z="$(($(($(($ENTITY1_Y-1))*$MAX_X))+$ENTITY1_X))"

  if [ "${matrix[$z]}" = "$ENUM_MATRIX_FOOD" ]; then

    matrix[$z]="$ENUM_MATRIX_LAND"

    ENTITY_ENERGY="$(($ENTITY_ENERGY+100))"

  fi

}

Теперь существо умеет есть, но еще не понимает, что ему это нужно. Нужно добавить аппарат поощрений

Результат:

https://vilkovsky@bitbucket.org/vilkovsky/evolutionary_programming.git

Далее работа будет продолжена в следующей главе

https://evolutionaryprogramming.blogspot.com/2020/11/evolutionary-programming-2.html