В этот раз взялся за реализацию генетического алгоритма на OCaml для решения задачи о 8 ферзях (не то, чтобы мне эта задача очень уж нравилась, но это пока тот уровень сложности, с которым я могу справиться без больших временных затрат).
Сам алгоритм довольно прост в реализации и больших вопросов не вызывает. По сути, мне нужно было разработать небольшой набор функций:
- mutate, чтобы проводить небольшие мутации;
- reproduce, чтобы создавать новые популяции на основе старых;
- test, чтобы проверять, есть ли в популяции решение задачи;
- find, чтобы запустить поиск решения.
Этого небольшого набора вполне достаточно, чтобы запустить поиск. Однако для меня интерес представляла не только разработка такого алгоритма, но и хотелось самому проверить эффективность некоторых эвристик при выборе родителей для следующей популяции, а заодно сделать что-то новое в OCaml. Из OCaml я выбрал модули, хоть я и применял их раньше, но в привычку не вошло (решение небольших задач на codingame не требует разработки своих модулей, а до больших задач ещё не дошёл). В качестве подопытных эвристик выступили стратегии:
- брать всех подряд, никого не выкидывать;
- выбрать одного лучшего (по сути, тут надежда только на мутации);
- выбирать двух лучших, остальных выбрасывать.
После того, как я описал базовый алгоритм и удостоверился, что он работает, начал формировать модуль.
module GA = struct end
Популяция представляет собой список из 4 списков, в каждом по 8 чисел:
module GA = struct let create_population () = List.init 4 (fun _ -> List.init 8 (fun _ -> Random.int 8)) end
Для проверки состояния доски использовал количество пар ферзей, которые не атакуют друг друга. Для 8 ферзей такое число равно 28, если никто не находится под ударом. На этом факте основаны две функции, одна для оценки близости состояния к решению, а вторая, является ли состояние решением (количество неатакующих пар == 28).
let evaluate population = let under_attack (l1, c1) (l2, c2) = c1 = c2 || (abs (l1 - l2)) = (abs (c1 - c2)) in let rec foldi i accum = function | [] -> assert false | [x] -> accum | x :: xs -> foldi (i + 1) (List.foldi xs ~init:accum ~f:(fun i' accum x' -> accum + if under_attack (i, x) ((i' + i + 1), x') then 0 else 1)) xs in foldi 0 0 population let is_safe population = (* This is only for 8 cells on board, * for other sizes max_value should be ((1 + n) / 2 * n). *) let max_value = 28 in evaluate population = max_value
Мутация и создание потомков простое и понятное.
let mutate population = let n = Random.int (List.length population) in List.mapi population ~f:(fun i x -> if i = n then (Random.int 8) else x) let reproduce population1 population2 = let n = Random.int (List.length population1) in let (left, _) = List.split_n population1 n in let (_, right) = List.split_n population2 n in left @ right
Далее идёт функция поиска решения. Она содержит в себе подсчёт количества шагов, а также возможность принимать функцию, которая будет фильтровать популяцию перед выбором родителей. Если такая функция не предоставлена, то для создания потомков будет использована вся популяция.
let find ?choose_parents population = let choose_parents = match choose_parents with | None -> (fun x -> x) | Some x -> x in let nextgen population = let population_size = List.length population in let population' = choose_parents population in let len = List.length population' in let rec aux i = if i > 0 then ( let n = Random.int len in let a = List.nth_exn population' n in let b = List.nth_exn population' n in let child = reproduce a b in if Random.int 10 < 3 then mutate child :: aux (i - 1) else child :: aux (i - 1) ) else [] in aux population_size in let steps_number = ref 0 in let rec find_solution population = steps_number := !steps_number + 1; if List.exists population ~f:is_safe then List.filter population ~f:is_safe |> List.hd_exn else nextgen population |> find_solution in let solution = find_solution population in (solution, !steps_number)
В коде, который должен запускать поиск решения, описаны также функции для фильтрации популяции. Чтобы сделать результаты воспроизводимыми, я везде использовал одни и те же числа для инициализации генератора случайных чисел.
let () = Random.init 10; (* Always init by the same number for testibility. *) let population = GA.create_population () in List.iter population ~f:(fun i -> printf "%s --> evaluate = %d\n" (GA.to_string i) (GA.evaluate i)); printf "\n"; let cmp a b = -(compare (GA.evaluate a) (GA.evaluate b)) in let choose_better_two population = match List.sort population ~cmp with | a :: b :: _ -> [a; b] | _ -> assert false in let choose_better_one population = [List.sort population ~cmp |> List.hd_exn] in let choices = [ None, "all"; Some (choose_better_one), "only better one"; Some (choose_better_two), "get best two" ] in let inits = [1; 10; 100; 42] in List.iter inits ~f:(fun init -> printf "Init by: %d\n" init; List.iter choices ~f:(fun (choose_parents, name) -> Random.init init; (* Always init by the same number for testibility. *) let solution, steps_number = match choose_parents with | None -> GA.find population | Some choose_parents -> GA.find ~choose_parents population in printf "%s -- Solved by <%s> in %d steps.\n" (GA.to_string solution) name steps_number ); printf "\n"; )
Результат
0 4 1 5 2 7 1 1 --> evaluate = 23 7 7 7 6 6 0 2 2 --> evaluate = 18 7 2 2 1 7 2 0 4 --> evaluate = 20 6 3 5 6 3 2 0 0 --> evaluate = 17 Init by: 1 7 1 4 2 0 6 3 5 -- Solved by <all> in 36126 steps. 5 3 6 0 7 1 4 2 -- Solved by <only better one> in 1180 steps. 2 4 1 7 5 3 6 0 -- Solved by <get best two> in 505 steps. Init by: 10 6 4 2 0 5 7 1 3 -- Solved by <all> in 48993 steps. 1 4 6 0 2 7 5 3 -- Solved by <only better one> in 57 steps. 0 4 7 5 2 6 1 3 -- Solved by <get best two> in 199 steps. Init by: 100 4 0 7 3 1 6 2 5 -- Solved by <all> in 27041 steps. 4 7 3 0 2 5 1 6 -- Solved by <only better one> in 527 steps. 0 4 7 5 2 6 1 3 -- Solved by <get best two> in 185 steps. Init by: 42 2 5 3 0 7 4 6 1 -- Solved by <all> in 2339 steps. 3 5 7 1 6 0 2 4 -- Solved by <only better one> in 2834 steps. 4 6 0 3 1 7 5 2 -- Solved by <get best two> in 1353 steps.
Заключение
Из результатов работы алгоритма видно, что при выборе лучших представителей популяции можно быстрее найти решение. Для сравнения стратегий <only better one> и <get best two> слишком мало данных. Возможно для каждой из этих стратегий нужно подбирать более подходящие вероятности мутаций. В данный момент оставлю вопрос открытым.