Changeset 1979 in genesis

Timestamp:

Apr 11, 2004, 1:05:07 AM (21 years ago)

Author:

lodewijk

Message:

het doet wat, en wat het doet doet het een hele hoop sneller dan de Python versie.

File:

• nodes/channelga.ml (modified) (9 diffs)

nodes/channelga.ml

@@ +1 @@
+(**
+  experiment met evolutionary programming voor de kanalenplanning
+  het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld
+  fout. wat er wel goed in zit is het parseren van de bestaande situatie en
+  het scoren van (nu random) configuraties.
+
+  de score functie is nu redelijk simplistisch:
+    - de score van een combinatie van twee interfaces op een node is 1 als er
+      twee of meer kanalen tussen zitten, en -1 als er 1 kanaal tussen zit, -5
+      als er geen kanaal tussen zit en -10 als de kanalen hetzelfde zijn
+    - de score van een node is de som van de scores van alle combinaties van
+      interfaces van die node, maal het aantal interfaces. dat laatste omdat
+      een positieve score hebben knapper is met meer interfaces dan met minder,
+      dus dat moet beloond. een negatieve score is erger met meer interfaces
+      (belangrijker node, waarschijnlijk) dan met minder, dus dat moet
+      bestraft.
+    - de totale score is de som van de scores van de nodes
+
+  het stukje "genetisch" aan het einde is afgeraffeld. mutation en
+  recombination gebeuren op de oplossing zelf ipv op een bitstring
+  representatie. selection is dom en neemt gewoon de helft beste oplossingen.
+
+  lvoge@cs.vu.nl *)
+
 (* a few constants *)
 let population_size = 20
@@ -4 +28 @@
 and mutation_rate = 0.05;;
 
-(* the type definitions. note the 'and' to string them together in a mutually
-   recursive blob so wi and node can refer to eachother *)
+(* the type definitions. note that Caml has trouble with mutually recursive
+   data structures. you can define them, you just can't ever instantiate them.
+   this is why the fields in wi are all loose references by way of strings *)
 type wi = {
-        winame: string;
-        node: node ref;
-        group: group ref;
-} and group = {
-        essid: string;
-        groupwis: wi ref list;
-} and node = {
-        nodename: string;
-        nodewis: wi list;
+        wi_name: string;
+        wi_nodename: string;
+        wi_essid: string;
+};;
+type group = {
+        group_essid: string;
+        mutable group_wis: wi list;
+};;
+type node = {
+        node_name: string;
+        node_wis: wi list;
 };;
 
@@ -21 +48 @@
 let groups = Hashtbl.create 4;;
 
-type score = int
- and channel = int;;
-
+(* some convenience functions *)
 let compose f g = fun x -> f(g(x));;
 let ($) = compose;;
 let maketuple a b = (a, b);;
+let head = List.hd;;
+let tail = List.tl;;
 (* given a hashtable, return all the keys as a list *)
 let keys t = Hashtbl.fold (fun k d a -> k::a) t [];;
@@ -37 +64 @@
         match l with
           []    -> []
-        | x::xs -> (List.map (maketuple x) xs)@(combinations xs)
-;;
+        | x::xs -> (List.map (maketuple x) xs)@(combinations xs);;
 
 (* given a configuration and two wi's, return the score *)
 let wi_score c wi1 wi2 =
-        let scoretable = [ ((>)  2,  1);
+        let scoretable = [ ((<=) 2,  1);
                            ((==) 2, -1);
                            ((==) 1, -5);
                            ((==) 0, -10) ] in
-        let channel1 = c !(wi1.group) in
-        let channel2 = c !(wi2.group) in
+        let channel1 = c wi1.wi_essid in
+        let channel2 = c wi2.wi_essid in
         let diff = abs (channel1 - channel2) in
         let rec runtable t = match t with
@@ -55 +81 @@
         runtable scoretable;;
 
+(* given a configuration and a node, return the score. this is simply the sum of
+   the scores of all the combinations of interfaces, written down as a fold for
+   efficiency *)
 let node_score c n =
         let foldfunc acc (wi1, wi2) = acc + (wi_score c wi1 wi2) in
-        List.fold_left foldfunc 0 (combinations n.nodewis);;
+        List.fold_left foldfunc 0 (combinations n.node_wis);;
 
 let score_configuration c (ns: node list) =
-        let mapper g = Hashtbl.find c g.essid in
-        let foldfunc acc n = acc + (node_score mapper n) in
+        let foldfunc acc n = acc + (node_score (Hashtbl.find c) n) in
         List.fold_left foldfunc 0 ns;;
-
-let add_wi_to_node n (w: wi) = { n with nodewis = (w::n.nodewis) };;
 
 (* given a filename, return a list of all the lines in the file with the given
@@ -78 +104 @@
         with End_of_file -> !result
 
+let parse_pair nodename (wname, gname) = 
+        let new_wi = { wi_name = wname; wi_nodename = nodename; wi_essid = gname} in
+        let foo = try
+                        let group = Hashtbl.find groups gname in
+                        group.group_wis <- new_wi::group.group_wis;
+                  with Not_found ->
+                        let group = { group_essid = gname; group_wis = [ new_wi ] } in
+                        print_string "added group ";
+                        print_string gname;
+                        print_newline();
+                        Hashtbl.add groups gname group in
+        new_wi
+
+let parse_fields fields = 
+        let nodename = head fields in
+        let rec makepairs l = match l with
+                                []              -> []
+                              | x::[]           -> assert false
+                              | a::b::xs        -> (a, b)::(makepairs xs) in
+        let wis = List.map (parse_pair nodename) (makepairs (tail fields)) in
+        let sorted_wis = List.sort compare wis in
+        let node = { node_name = nodename; node_wis = sorted_wis } in
+        Hashtbl.add nodes nodename node
+
 let parse_file fname =
-        let bogus_node = { nodename = "foo"; nodewis = [] } in
-        Hashtbl.add nodes fname bogus_node;
-        Hashtbl.add groups fname 1;
+        let spacere = Str.regexp " " in
+        List.iter (parse_fields $ (Str.split spacere)) (snarf_lines fname)
         ;;
 
-let random_configuration =
+let random_configuration groups =
         let conf = Hashtbl.create 30 in
         Hashtbl.iter (fun k d -> Hashtbl.add conf k (1 + (Random.int 12))) groups;
         conf
 
+(* Mutate the configuration in the given population at the given offset *)
 let mutate p i = 
         Hashtbl.iter (fun essid chan -> let f = Random.float 1.0 in
@@ -94 +144 @@
                                           Hashtbl.replace p.(i) essid (1 + (Random.int 13))) p.(i);;
 
+let print_conf conf = 
+        let print_wi wi = wi.wi_name ^ ": " ^ (string_of_int (Hashtbl.find conf wi.wi_essid)) in
+        let wis node = List.fold_left (fun acc wi -> acc ^ " " ^ (print_wi wi)) "" node.node_wis in
+        let sorted_nodes = List.sort (fun a b -> compare (a.node_name) (b.node_name)) (values nodes) in
+        List.iter (fun n -> print_string (n.node_name ^ ":" ^ (wis n) ^ "\n")) sorted_nodes
+
 let main = 
-        List.iter parse_file (snarf_lines Sys.argv.(1));
+        parse_file Sys.argv.(1);
         Random.self_init();
-        let population = Array.init population_size (fun _ -> random_configuration) in
+        let population = Array.init population_size (fun _ -> random_configuration groups) in
         let last_high_score = ref (-1000000) in
         let iterations_since_new_high_score = ref 0 in
+        let generation = ref 0 in
         let all_nodes = values nodes in
         while !iterations_since_new_high_score < max_stagnant_iterations do
@@ -112 +169 @@
                 let score_pop = Array.map (fun c -> ((score_configuration c all_nodes), c)) population in
                 (* sort on the first field *)
-                Array.sort (fun x y -> compare (fst x) (fst y)) score_pop;
+                Array.sort (fun x y -> compare (fst y) (fst x)) score_pop;
+                Array.blit (Array.map snd score_pop) 0 population 0 (Array.length score_pop);
                 (* now look at the best score and update the highscore if
                    necessary *)
@@ -120 +178 @@
                         iterations_since_new_high_score := 0
                 end;
-                (*print_int high_score;*)
-                print_int !iterations_since_new_high_score;
-                print_newline();
-                incr iterations_since_new_high_score
+                assert (!last_high_score >= high_score);
+                if (!generation mod 10) == 0 then begin
+                        print_int !generation;
+                        print_string ": ";
+                        print_int !last_high_score;
+                        print_newline();
+                end;
+                incr iterations_since_new_high_score;
+                incr generation
         done;
-        ()
-;;
+        print_conf population.(0);;
 
 main