O problema de partição de números consiste em: dado um conjunto de N números, o objetivo é subdividi-lo em dois subconjuntos (chamados de partições) de tal forma que, a diferença entre os valores das somas dos números dessas duas partições seja a menor possível. Por exemplo, considere o seguinte conjunto com quatro números (23, 20, 56, 48). As partições (20,56) e (23,48) consistem no particionamento ótimo para este conjunto e, seu valor é 5. Apesar da simplicidade do enunciado, este é um problema de otimização combinatória que pertence à classe NP-difícil. Observe que, para um conjunto com N números têm-se 2N possíveis maneiras de subdividi-lo em duas partições.

Nosso problema consiste em dado uma seqüência [10,20,30,11,25,23,32,9,7,19,17,31,48,27,5,21,35,13,38,16,14,33,5] devemos criar um vetor de sinais (- ou +) para cada numero disposto, de modo a alcançarmos o menor valor (tendendo a 0) considerando o módulo do resultado das operações realizadas.

EX: para o vetor [10,20,30,11] geramos um vetor [1,1,0,0] considerei para esse exemplo que um representa + e 0 representa -, sendo assim nosso vetor seria [+,+,-,-]. O que geraria +10+20-30-11, resultando no valor 11, considerando seu módulo.

Entendido esse conceito vamos ao código.

Criaremos uma classe chamada Individuo com dois atributos @code e @value que recebem respectivamente o código binário (que representa os sinais) e o valor da função objetivo (ou em nosso caso o resultado da sentença) daquele individuo em questão.

[ruby]
class Individuo
attr_reader :code,:value
def initialize
@code = ((0+rand(8_388_608)).to_s(base=2)).rjust(23,"0")
@value = to_value(@code)
end

def to_value(binary)
a = [10,20,30,11,25,23,32,9,7,19,17,31,48,27,5,21,35,13,38,16,14,33,5]
sign = {"0"=>-1,"1"=>1}
value = index = 0
binary.each_char do |c|
value = value+a[index]*sign[c]
index+=1
end
(value<0 ? value*-1:value ) #MODULO
end

end
[/ruby]

E pronto, agora podemos gerar quantos indivíduos quisermos sem o menor esforço. Vou dar um exemplo de criação de 100 individuos.

[ruby]
população = 100.times.collect{Individuo.new}
[/ruby]

Não é tão difícil quanto parece. Podemos implementar uma segunda classe mais bonitinha para realizarmos nossos experimento abaixo um exemplo de implementação da classe Raca (Raça) que vai nos dar uma interface facilitadora para gerar nossa população.

[ruby]
require 'individuo'
class Raca

attr_reader :populacao,:quantidade,:populacao_ordenada
attr_accessor :valor_total

def initialize(quantidade)
@quantidade = quantidade
@populacao = criar_populacao(@quantidade)
end

#método que realiza a criação da população Inicial
def criar_populacao(quantidade)
quantidade.times.collect{Individuo.new}
end

#apenas ordena o vetor do melhor idividuo para o pior
def selecao_natural
@populacao.collect { |ind| [ind.value,ind.code] }.sort
end

#sobrescrevendo o to_s para uma visão melhor da população
def to_s
out =  "Valor".ljust(10)+"     Código Genético ".ljust(25)+"\n\n"
@populacao.each do |individuo|
out << "#{individuo.value.to_s.ljust(10)} #{individuo.code.ljust(25)}\n"
end
out
end
end
#rodando código
anfibios = Raca.new(12)
puts anfibios
[/ruby]

Esse código tem como resultado algo parecido com isso :

Valor          Código Genético  

1          11100010001111000001100 
73         00110110100011000001100 
29         10001011010011010011100 
237        01111011111110000111110 
5          11101000000110001101100 
99         01000010101001000011011 
173        01111110011110101001101 
35         11010011100010100010110 
109        10100010101000110001111 
23         10011001001101000110111 
135        01000111111101101011010 
119        10001100011001110010000

O Código está disponível aqui: [download id="6"]