Генетический алгоритм для умных проекта алгоритмы


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

Для представителя пример ниже, любые идеи о том, что делает его более "Руби нравится"?

# Genetic Algorithm in the Ruby Programming Language

# The Clever Algorithms Project: http://www.CleverAlgorithms.com
# (c) Copyright 2010 Jason Brownlee. Some Rights Reserved. 
# This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 2.5 Australia License.

def onemax(bitstring)
  sum = 0
  bitstring.size.times {|i| sum+=1 if bitstring[i].chr=='1'}
  return sum
end

def random_bitstring(num_bits)
  return (0...num_bits).inject(""){|s,i| s<<((rand<0.5) ? "1" : "0")}
end

def binary_tournament(pop)
  i, j = rand(pop.size), rand(pop.size)
  j = rand(pop.size) while j==i
  return (pop[i][:fitness] > pop[j][:fitness]) ? pop[i] : pop[j]
end

def point_mutation(bitstring, rate=1.0/bitstring.size)
  child = ""
   bitstring.size.times do |i|
     bit = bitstring[i].chr
     child << ((rand()<rate) ? ((bit=='1') ? "0" : "1") : bit)
  end
  return child
end

def crossover(parent1, parent2, rate)
  return ""+parent1 if rand()>=rate
  point = 1 + rand(parent1.size-2)
  return parent1[0...point]+parent2[point...(parent1.size)]
end

def reproduce(selected, pop_size, p_cross, p_mutation)
  children = []  
  selected.each_with_index do |p1, i|
    p2 = (i.modulo(2)==0) ? selected[i+1] : selected[i-1]
    p2 = selected[0] if i == selected.size-1
    child = {}
    child[:bitstring] = crossover(p1[:bitstring], p2[:bitstring], p_cross)
    child[:bitstring] = point_mutation(child[:bitstring], p_mutation)
    children << child
    break if children.size >= pop_size
  end
  return children
end

def search(max_gens, num_bits, pop_size, p_crossover, p_mutation)
  population = Array.new(pop_size) do |i|
    {:bitstring=>random_bitstring(num_bits)}
  end
  population.each{|c| c[:fitness] = onemax(c[:bitstring])}
  best = population.sort{|x,y| y[:fitness] <=> x[:fitness]}.first  
  max_gens.times do |gen|
    selected = Array.new(pop_size){|i| binary_tournament(population)}
    children = reproduce(selected, pop_size, p_crossover, p_mutation)    
    children.each{|c| c[:fitness] = onemax(c[:bitstring])}
    children.sort!{|x,y| y[:fitness] <=> x[:fitness]}
    best = children.first if children.first[:fitness] >= best[:fitness]
    population = children
    puts " > gen #{gen}, best: #{best[:fitness]}, #{best[:bitstring]}"
    break if best[:fitness] == num_bits
  end
  return best
end

if __FILE__ == $0
  # problem configuration
  num_bits = 64
  # algorithm configuration
  max_gens = 100
  pop_size = 100
  p_crossover = 0.98
  p_mutation = 1.0/num_bits
  # execute the algorithm
  best = search(max_gens, num_bits, pop_size, p_crossover, p_mutation)
  puts "done! Solution: f=#{best[:fitness]}, s=#{best[:bitstring]}"
end


1297
17
задан 28 января 2011 в 05:01 Источник Поделиться
Комментарии
4 ответа

Сначала обратите внимание на общий дизайн: вы использовать всех HashMap, чтобы представлять членов общества. Я бы порекомендовал вам создать небольшой класс, чтобы представить их:

class Individual
include Comparable

attr_reader :bitstring, :fitness

def initialize(bitstring)
@bit_string = bitstring
@fitness = onemax(bitstring)
end

def <=>(other)
fitness <=> other.fitness
end
end

Вы будете теперь использовать индивидуальные.новый(битовая) , чтобы создать нового человека (который автоматически рассчитать свой собственный фитнес центр) и индивидуальные.битовая и индивидуальных.фитнес , чтобы получить индивидуальный битовая или фитнес-соответственно.

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

Также обратите внимание, что я включил сопоставимы, реализация <=> на основе фитнес -. Это означает, что теперь вы можете сравнивать людей друг с другом таким образом, что индивид-это больше, чем другому, если, и только если фитнес больше. Это позволяет использовать > на двух лиц, а также методы, как максимум , чтобы получить особь с наибольшей пригодности из массива индивидов. Это также позволяет звонить сортировки на массиве лиц без прохождения блока. Это позволит упростить код в некоторых местах.


В комментарии Вы упомянули, что вы не хотите использовать классы. Однако я все-таки думаю, что это бы значительно улучшить ваш дизайн, чтобы логика при создании новых физических и расчета их пригодности в одном месте, так что вы должны, по крайней мере, вынести его в метод такой:

def create_individual(bitstring)
{:bitstring => bitstring, :fitness => onemax(bitstring)}
end


Теперь некоторые заметки о конкретной части кода:

bitstring.size.times {|i| sum+=1 if bitstring[i].chr=='1'}

Как уже упоминалось, это может легко быть заменен на вызов графа. Однако в целом я хочу отметить, что это хорошая практика, чтобы избежать индексных петли там, где это возможно, так что если графа не существует, я писал выше как это:

bitstring.each_char {|c| sum+=1 if c == '1'}

Или для 1.8.6 совместимость:

bitstring.each_byte {|b| sum+=1 if b.chr == '1'}


(0...num_bits).inject(""){|s,i| s<<((rand<0.5) ? "1" : "0")}

При работе с вкачать, это обычно хорошая идея, чтобы сохранить функции, таким образом, это более легко и понятно. Часто вы можете отделить логику генерации элементов из логики сочетая их, используя карту , прежде чем впрыснуть. Это сделало бы ваш код выглядеть так:

(0...num_bits).map {|i| (rand<0.5) ? "1" : "0"}.inject("") {|s,i| s<<i}

Теперь обратите внимание на две вещи здесь:


  1. Всякий раз, когда вы называете карту на диапазоне от 0 до некоторого размера, вы скорее хотите использовать массив.новый(размер) {блок} , которая создает массив заданного размера путем вызова блока размер раз.

  2. Чем меньше впрыснуть теперь гораздо проще понять, но случается, эквивалентно вызову присоединиться, так что давайте просто сделать это.

Так что ваш код становится:

Array.new(num_bits) { (rand<0.5) ? "1" : "0" }.join

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


(pop[i][:fitness] > pop[j][:fitness]) ? pop[i] : pop[j]

Благодаря индивидуальному классу это теперь выглядит так:

(pop[i] > pop[j]) ? pop[i] : pop[j]

Это не сильно отличается, но учтите, что он теперь имеет вид (х > у) ? Х : Y, который, кстати, означает "не более двух объектов". Другими словами, мы можем упростить этот код, используя максимальный метод:

[ pop[i], pop[j] ].max


bitstring.size.times do |i|
bit = bitstring[i].chr

Опять же это должно быть битовая.each_char делать |бит| или битовая.each_byte у |б| бит = б.ЧР.


""+parent1 if rand()>=rate

Я не уверен, что ""+ это должен делать здесь. Удалить его. Обратите внимание, что ""+Х - это не способ превратить х в строку в Ruby (как это было бы в например, Java). Звоню ""+х когда х не является строкой (или "утки-строку"), приведет к ошибке.

Тот факт, что вы используете ""+ для создания копии является менее очевидной (при этом абзацем выше). Если вы используете ДУП способ, чья единственная цель его заключается в создании копии, вместо этого, он будет гораздо более понятным.


Я бы также изменить кроссовера способ, чтобы вернуть человека, а не строку, которая делает код немного проще.

22
ответ дан 28 января 2011 в 01:01 Источник Поделиться

Библиотека Рубин является достаточно мощным:

onemax(битовая) можно просто битовая.графа('1')

random_bitstring(num_bits) наверное лучше реализован как Рэнд(2**num_bits).to_s(2)

Первая вещь, чтобы проверить это http://ruby-doc.org/core-2.0/Enumerable.html

7
ответ дан 28 января 2011 в 07:01 Источник Поделиться

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

Единственный раз вы специально не понадобится возвращать вам даже не нужно использовать возврат, если вы не возвращающих несколько значений:

def f
[1,2]
end

a,b = f

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

5
ответ дан 28 января 2011 в 05:01 Источник Поделиться

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

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


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

  • "Поиск" определение метода были в начале файла, прямо под хэш с описанием конфига. (Вызов метода по-прежнему происходит внизу в вашем случае файл раздел.)

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

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

Так

children.sort!{|x,y| y[:fitness] <=> x[:fitness]}

становится

children.sort!{ |x,y| y[:fitness] <=> x[:fitness] }

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

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

def crossover(parent1, parent2, rate)
return ""+parent1 if rand()>=rate
point = 1 + rand(parent1.size-2)
return parent1[0...point]+parent2[point...(parent1.size)]
end

становится

def crossover(parent1, parent2, rate)
return "" + parent1 if rand() >= rate
point = 1 + rand(parent1.size-2)
return parent1[0...point] + parent2[point...(parent1.size)]
end

И теперь я получаю гнида придирчивые...так что я сделал сейчас.

4
ответ дан 30 января 2011 в 04:01 Источник Поделиться