Changeset 1999 in genesis

Timestamp:

Apr 13, 2004, 11:10:18 PM (21 years ago)

Author:

lodewijk

Message:

• n-point crossover operator toegevoegd
• die operator in de 'recombine' functie gehangen, geconstateerd dat de oplossingen er niet beter van werden en het geheel wel een stuk trager werd, dus maar weer weggecommentaard.

File:

• nodes/channelea.ml (modified) (5 diffs)

nodes/channelea.ml

@@ -119 +119 @@
 (** Shorthand for List.tail *)
 let tail = List.tl
+let even x = (x mod 2) == 0
+(*let shuffle = Array.sort (fun _ _ -> 1 - Random.int(2))*)
 let just x = match x with
                Nothing -> assert false
@@ -208 +210 @@
         let print_node n = print_string (n.node_name ^ ": " ^ (wis n) ^ "\n") in
         List.iter print_node sorted_nodes
+
+(** n-point crossover operator. pick n points along the length of the parents, 
+    produce a child by copying from one parent, switching parents when hitting a
+    chosen crossover point *)
+let crossover n c1 c2 = 
+        let keys1 = keys (c1.conf) in
+        let numkeys1 = List.length keys1 in
+        let pickpoint i = (if even i then c1.conf else c2.conf),
+                          (if i < n then (Random.int numkeys1) else numkeys1) in
+        let crosspoints = Array.init (n + 1) pickpoint in
+        let result = Hashtbl.create (List.length keys1) in
+        let i = ref 0 in
+        Array.sort (fun a b -> compare (snd a) (snd b)) crosspoints;
+        Array.iter (fun (h, p) -> while !i < p do
+                                        let key = List.nth keys1 !i in
+                                        Hashtbl.add result key (Hashtbl.find h key);
+                                        incr i
+                                  done) crosspoints;
+        assert ((List.length (keys result)) == (List.length keys1));
+        { score = 0; conf = result }
 
 (** Generalized evolutionary algorithm driver. 
@@ -223 +245 @@
         let generation = ref 0 in
         let all_nodes = values nodes in
-        let iterate = recombine $ mutate $ evaluate $ select in
+        (*let iterate = recombine $ mutate $ evaluate $ select in*)
+        let iterate = select $ evaluate $ mutate $ recombine in 
         while !iterations_since_new_high_score < max_stagnant_iterations do
                 let newpop = iterate population in
-                Array.sort (fun a b -> compare b.score a.score) newpop;
+                assert ((Array.length newpop) == population_size);
                 copyarray newpop population;
                 let high_score = population.(0).score in
@@ -337 +360 @@
         let evaluate_hash = score_configuration all_nodes in
         let initialize () = Array.init population_size (fun _ -> random_configuration groups evaluate_hash) in
-        let recombine x = x in
+        let recombine pop = pop in
+(*
+                let numoffspring = Random.int population_size in
+                let children = Array.init numoffspring (fun _ -> 
+                        let father = pop.(Random.int population_size) in
+                        let mother = pop.(Random.int population_size) in
+                        crossover 2 father mother) in
+                Array.append pop children in *)
         let maxchannel essid =
                 let group = Hashtbl.find groups essid in
@@ -357 +387 @@
                 Array.iter (fun c -> c.score <- evaluate_hash c.conf) population;
                 population in
-        let select p = Array.sub p 0 ((Array.length p) / 2) in
+        let select p = 
+                Array.sort (fun a b -> compare b.score a.score) p;
+                (*shuffle p;*)
+                Array.sub p 0 population_size in
         let best = evolutionary_algorithm initialize recombine mutate evaluate select in
         print_conf best.conf;;