crossover_ga_binary was unclassical badly documented and untested 78/14578/7
Michael BAUDIN [Wed, 28 May 2014 08:09:30 +0000 (10:09 +0200)]
Change-Id: I36deba4a44e5653b6a31d0811b1dcd5c15ab3612

scilab/CHANGES_5.5.X
scilab/modules/genetic_algorithms/help/en_US/utilities/crossover_ga_binary.xml
scilab/modules/genetic_algorithms/macros/crossover_ga_binary.sci
scilab/modules/genetic_algorithms/tests/unit_tests/crossover_ga_binary.dia.ref
scilab/modules/genetic_algorithms/tests/unit_tests/crossover_ga_binary.tst

index e9ac823..5390baf 100644 (file)
@@ -110,6 +110,12 @@ Scilab Bug Fixes
 * Bug #13409 fixed - permute(x, dims) failed when dims was greater than the dimensions of size(x)
                      now permute treats extra dimensions as 1.
 
+* Bug #13418 fixed - Help page for crossover_ga_binary was unclear.
+                     Also added mix to check the crossover positions.
+
+* Bug #13424 fixed - crossover_ga_binary algorithm was not the classical point crossover one.
+                     Also fixed the usage of binary length.
+
 * Bug #13425 fixed - optim_ga and optim_moga needed optimization.
 
 * Bug #13435 fixed - Windows version crashes when calling xmlRemove on the first child.
index 16a9e19..faec260 100644 (file)
@@ -2,6 +2,8 @@
 <!--
  * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
  * Copyright (C) 2008 - Yann COLLETTE <yann.collette@renault.com>
+ * Copyright (C) 2014 - Michael BAUDIN <michael.baudin@contrib.scilab.org>
+ * Copyright (C) Scilab Enterprises - 2014 - Pierre-Aime AGNEL
  *
  * This file must be used under the terms of the CeCILL.
  * This source file is licensed as described in the file COPYING, which
@@ -17,7 +19,7 @@
     </refnamediv>
     <refsynopsisdiv>
         <title>Calling Sequence</title>
-        <synopsis>[Crossed_Indiv1,Crossed_Indiv2] = crossover_ga_binary(Indiv1,Indiv2,param)</synopsis>
+        <synopsis>[Crossed_Indiv1, Crossed_Indiv2, mix] = crossover_ga_binary(Indiv1, Indiv2, param)</synopsis>
     </refsynopsisdiv>
     <refsection>
         <title>Arguments</title>
@@ -25,6 +27,7 @@
             <varlistentry>
                 <term>Indiv1</term>
                 <listitem>
+                    <para>A string</para>
                     <para>the first individual (here a binary code) to be
                         crossed-over.
                     </para>
             <varlistentry>
                 <term>Indiv2</term>
                 <listitem>
+                    <para>A string</para>
                     <para>the second individual to be crossed-over.</para>
                 </listitem>
             </varlistentry>
             <varlistentry>
                 <term>param</term>
                 <listitem>
-                    <para>a list of parameters. </para>
+                    <para>a list of parameters.</para>
                     <itemizedlist>
                         <listitem>
-                            <para> 'binary_length': the length of the binary code. </para>
+                            <para>
+                                <literal>"binary_length"</literal>: an integer, the length of the binary
+                                code (default 8).
+                            </para>
                         </listitem>
                         <listitem>
-                            <para> 'multi_cross': a boolean. If %T then we allow several
-                                cuts in the binary code. 
+                            <para>
+                                <literal>"multi_cross"</literal>: a boolean. If <literal>%T</literal> then we allow several
+                                cuts in the binary code (default <literal>%F</literal>).
                             </para>
                         </listitem>
                         <listitem>
-                            <para> 'multi_cross_nb': the number of cuts in the binary code.
-                                Only used when multi_cross is set to %T.
+                            <para>
+                                <literal>"multi_cross_nb"</literal>: an integer, the number of cuts in the binary code.
+                                Only used when multi_cross is set to %T (default 2).
                             </para>
                         </listitem>
                     </itemizedlist>
@@ -60,6 +69,7 @@
             <varlistentry>
                 <term>Crossed_Indiv1</term>
                 <listitem>
+                    <para>A string</para>
                     <para>The first individual obtained by the cross-over
                         function.
                     </para>
             <varlistentry>
                 <term>Crossed_Indiv2</term>
                 <listitem>
+                    <para>A string</para>
                     <para>The second individual obtained by the cross-over
                         function.
                     </para>
                 </listitem>
             </varlistentry>
+            <varlistentry>
+                <term>mix</term>
+                <listitem>
+                    <para>A vector of integers</para>
+                    <para>The positions the crossover occurred.</para>
+                </listitem>
+            </varlistentry>
         </variablelist>
     </refsection>
     <refsection>
         <title>Description</title>
-        <itemizedlist>
-            <listitem>
-                <para>This function implements a classical binary cross-over.</para>
-            </listitem>
-        </itemizedlist>
+        <para>This function implements a classical binary cross-over.</para>
+        <para>
+            <literal>crossover_ga_binary(Indiv1, Indiv2)</literal> generates
+            the crossover between <varname>Indiv1</varname> and <varname>Indiv2</varname>
+            by merging the characters from each string.
+        </para>
+        <para>
+            A position <literal>i</literal> is chosen randomly
+            between 1 and the length of the binary code.
+        </para>
+        <para>
+            Then <literal>Indiv1</literal> and <literal>Indiv2</literal>
+            are split in two parts:
+            the first <literal>i</literal> characters (the head),
+            and the remaining characters (the tail).
+            The crossover swaps the tails of the binary codes.
+        </para>
+        <para>
+            The following schema presents the crossover:
+            <programlisting role="explanation"><![CDATA[
+                Indiv1=[H1 T1]
+                Indiv2=[H2 T2]
+                Crossed_Indiv1=[H1 T2]
+                Crossed_Indiv2=[H2 T1]
+                ]]></programlisting>
+        </para>
+        <para>
+            The behaviour of the function can be modified with the use of <varname>param</varname>:
+        </para>
+        <variablelist>
+            <varlistentry>
+                <term>
+                    binary_length
+                </term>
+                <listitem>
+                    <para>
+                        changes the minimal length of the binary code, by default 8 characters.
+                    </para>
+                    <para>
+                        Binary code for <varname>Indiv1</varname> or <varname>Indiv2</varname>
+                        of lower length are zero padded to the right to be of
+                        <literal>binary_length</literal> length or <literal>max([length(Indiv1), length(Indiv2)])</literal>
+                        whichever is greater.
+                    </para>
+                </listitem>
+            </varlistentry>
+            <varlistentry>
+                <term>multi_cross</term>
+                <listitem>
+                    <para>
+                        if set to <literal>%T</literal> multiple crossovers
+                        can happen (default <literal>%F</literal>)
+                    </para>
+                </listitem>
+            </varlistentry>
+            <varlistentry>
+                <term>multi_cross_nb</term>
+                <listitem>
+                    <para>
+                        the number of locations for crossovers.
+                        (default 2 if
+                        multi_cross is set to <literal>%T</literal>, 1 otherwise)
+                    </para>
+                </listitem>
+            </varlistentry>
+        </variablelist>
+    </refsection>
+    <refsection>
+        <title> Random number generator </title>
+        <para>
+            <literal>crossover_ga_binary</literal> is based
+            on <link linkend="grand">grand</link>
+            for generating the random samples.
+            Use <literal>grand("setsd", seed)</literal> to change the seed
+            for <literal>crossover_ga_binary</literal>.
+        </para>
+        <programlisting role="example"><![CDATA[
+            seed = getdate("s");
+            grand("setsd", seed); //sets the seed to current date
+
+            seed = 0;
+            grand("setsd", seed); //sets the seed to default value
+            ]]>
+        </programlisting>
+    </refsection>
+    <refsection>
+        <title>Examples</title>
+        <programlisting role="example"><![CDATA[
+            A = "11100000"
+            B = "00011111"
+            [A_crossed, B_crossed, mix] = crossover_ga_binary(A, B)
+
+            C = dec2bin(2^16 - 1, 16)
+            D = "0"
+            param = init_param();
+            param = add_param(param, "binary_length", 16);  // Code of length 16
+            param = add_param(param, "multi_cross", %T);    // Multiple Crossover
+            param = add_param(param, "multi_cross_nb", 3);  // Occurs over 3 locations
+
+            [C_crossed, D_crossed, mix] = crossover_ga_binary(C, D, param)
+ ]]></programlisting>
     </refsection>
     <refsection role="see also">
         <title>See Also</title>
             <member>
                 <link linkend="optim_ga"> optim_ga </link>
             </member>
+            <member>
+                <link linkend="grand">grand</link>
+            </member>
         </simplelist>
     </refsection>
 </refentry>
index 4058555..61fa265 100644 (file)
@@ -1,5 +1,7 @@
 // Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
 // Copyright (C) 2008 - Yann COLLETTE <yann.collette@renault.com>
+// Copyright (C) 2014 - Michael BAUDIN <michael.baudin@contrib.scilab.org>
+// Copyright (C) Scilab Enterprises - 2014 - Pierre-Aime AGNEL
 //
 // This file must be used under the terms of the CeCILL.
 // This source file is licensed as described in the file COPYING, which
@@ -7,39 +9,82 @@
 // are also available at
 // http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt
 
-function [Crossed_Indiv1, Crossed_Indiv2] = crossover_ga_binary(Indiv1,Indiv2,param)
+//==============================================================================
+// crossover_ga_binary
+//==============================================================================
+// INPUT
+//    Indiv1 = A string representing a binary code
+//    Indiv2 = A strings representing a binary code
+//    param  = A plist with the following parameters
+//        binary_length  = an integer, the length of the binary code (def. 8)
+//        multi_cross    = a boolean, flag for multiple crossovers (def. %f)
+//        multi_cross_nb = an integer, number of multiple crossovers (def. 2)
+//
+// OUTPUT
+//    Crossed_Indiv1 = A string,
+//                     result of the cross over for Indiv1
+//    Crossed_Indiv2 = A string,
+//                     result of the cross over for Indiv2
+//    mix            = a vector of double, the positions
+//                      where the crossover was done
+//
+// DESCRIPTION
+//    Function crossover_ga_binary generates the crossover between
+//    Indiv1 and Indiv2 taken as binary code.
+//
+//    Without any additional parameters crossover_ga_binary(Indiv1, Indiv2)
+//    returns the crossover occruring on a single random location
+//
+//    crossover_ga_binary(Indiv1, Indiv2, param) modifies its behaviour
+//    with the values of param:
+//        binary_length:
+//            length of the binary code (default 8)
+//        multi_cross:
+//            if set to %t multiple crossover can happen (default %f)
+//        multi_cross_nb:
+//            the maximal number of possible crossovers.
+//            (default 2 if
+//            multi_cross is set to %t, 1 otherwise)
+//            At least one crossover will occur.
+
+function [Crossed_Indiv1, Crossed_Indiv2, mix] = crossover_ga_binary(Indiv1,Indiv2,param)
+
+    fname = "crossover_ga_binary";
     if ~isdef("param","local") then
         param = [];
     end
 
     // We deal with some parameters to take into account the boundary of the domain and the neighborhood size
-    [BinLen,err]       = get_param(param,"binary_length",8);
-    [MultiCross,err]   = get_param(param,"multi_cross",%F);
-    [MultiCrossNb,err] = get_param(param,"multi_cross_nb",2);
+    [BinLen, errLen] = get_param(param, "binary_length", 8);
+    [MultiCross, errMultiCross] = get_param(param, "multi_cross", %F);
+    if MultiCross
+        [MultiCrossNb, errMultiCrossNb] = get_param(param, "multi_cross_nb", 2);
+    else
+        MultiCrossNb = 1;
+    end
+
+    len1 = length(Indiv1);
+    len2 = length(Indiv2);
+    BinLen = max([len1, len2, BinLen]);
+    if len1 < BinLen
+        Indiv1 = strcat(string(zeros(1, BinLen - len1))) + Indiv1; //0 padding on the right
+    end
+    if len2 < BinLen
+        Indiv2 =  strcat(string(zeros(1, BinLen - len2))) + Indiv2; //0 padding on the right
+    end
 
-    if ~MultiCross then
-        mix = ceil((length(Indiv1)-1)*grand(1,1,"def"))+1;
+    // Crossover positions selection
+    mix = unique(gsort(sample(MultiCrossNb, 1:BinLen-1), "g", "i"))';
+    Crossed_Indiv1 = Indiv1;
+    Crossed_Indiv2 = Indiv2;
 
-        part1_1 = part(Indiv1,1:mix);
-        part1_2 = part(Indiv1,mix+1:length(Indiv1));
-        part2_1 = part(Indiv2,1:mix);
-        part2_2 = part(Indiv2,mix+1:length(Indiv2));
+    for j = 1:size(mix, "*")
+        H1 = part(Crossed_Indiv1, 1:mix(j)); //Head for Indiv1
+        T1 = part(Crossed_Indiv1, (mix(j) + 1):BinLen); //Tail for Indiv1
+        H2 = part(Crossed_Indiv2, 1:mix(j)); //Head for Indiv2
+        T2 = part(Crossed_Indiv2, (mix(j) + 1):BinLen); //Tail for Indiv2
 
-        Crossed_Indiv1 = strcat([part1_1 part2_2]);
-        Crossed_Indiv2 = strcat([part1_2 part2_1]);
-    else
-        mix = ceil((length(Indiv1)-1)*grand(MultiCrossNb,1,"def"))+1;
-        mix = -unique(gsort(-mix));
-        Crossed_Indiv1 = Indiv1;
-        Crossed_Indiv2 = Indiv2;
-        for i=1:length(mix)
-            part1_1 = part(Crossed_Indiv1,1:mix(i));
-            part1_2 = part(Crossed_Indiv1,mix(i)+1:length(Crossed_Indiv1));
-            part2_1 = part(Crossed_Indiv2,1:mix(i));
-            part2_2 = part(Crossed_Indiv2,mix(i)+1:length(Crossed_Indiv2));
-
-            Crossed_Indiv1 = strcat([part1_1 part2_2]);
-            Crossed_Indiv2 = strcat([part1_2 part2_1]);
-        end
+        Crossed_Indiv1 = [H1 + T2];
+        Crossed_Indiv2 = [H2 + T1];
     end
 endfunction
index e4a5594..3789362 100644 (file)
@@ -1,10 +1,86 @@
 // Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
 // Copyright (C) 2008 - Yann COLLETTE <yann.collette@renault.com>
+// Copyright (C) Scilab Enterprises - 2014 - Pierre-Aime Agnel
 //
 // This file must be used under the terms of the CeCILL.
 // This source file is licensed as described in the file COPYING, which
 // you should have received as part of this distribution.  The terms
 // are also available at
 // http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt
+// <-- CLI SHELL MODE -->
 [Crossed_Indiv1, Crossed_Indiv2] = crossover_ga_binary('11111111','00000000',[]);
 if (length(Crossed_Indiv1)~=8) | (length(Crossed_Indiv2)~=8) then bugmes();quit;end
+//==============================================================================
+// Nominal Behaviour
+//==============================================================================
+param = init_param("binary_length", 8, "multi_cross", %F, "multi_cross_nb", 1);
+A = "11111111";
+B = "00000000";
+// Reinitialize the seed
+grand("setsd", 0);
+[A_crossed, B_crossed, mix] = crossover_ga_binary(A, B);
+// Reinitialize the seed
+grand("setsd", 0);
+[A_crossed_p, B_crossed_p, mix] = crossover_ga_binary(A, B, param);
+//======================================
+// Check default behaviour of param
+//======================================
+assert_checkequal(A_crossed_p, A_crossed);
+assert_checkequal(B_crossed_p, B_crossed);
+assert_checkequal(size(mix, "*"), 1);
+//======================================
+// Check the crossover occurred
+//======================================
+// Heads
+assert_checkequal(part(A, 1:mix), part(A_crossed, 1:mix));
+assert_checkequal(part(B, 1:mix), part(B_crossed, 1:mix));
+// Tails
+assert_checkequal(part(A, (mix + 1):$), part(B_crossed, (mix + 1):$));
+assert_checkequal(part(B, (mix + 1):$), part(A_crossed, (mix + 1):$));
+//======================================
+// Binary length
+//======================================
+param = set_param(param, "binary_length", 16);
+A = dec2bin(2^16 - 1, 16); // 11111111 11111111
+B = dec2bin(0, 16); // 00000000 00000000
+[A_crossed, B_crossed, mix] = crossover_ga_binary(A, B, param);
+assert_checkequal(length(A_crossed), 16);
+assert_checkequal(length(B_crossed), 16);
+//======================================
+// Multiple Crossover
+//======================================
+param = init_param("binary_length", 16, "multi_cross", %T);
+s_mix = 0;
+iter = 0;
+// By default 2 crossovers
+while s_mix < 2 & iter <= 100
+    [A_crossed, B_crossed, mix] = crossover_ga_binary(A, B, param);
+    s_mix = size(mix, "*");
+    iter = iter + 1;
+end
+// Warning probabilistic test
+assert_checktrue(s_mix == 2); // we have reached one mix of length 2
+assert_checkfalse(iter>=100); // we have done it under 100 tries
+assert_checkequal(part(A_crossed, 1:mix(1)), part(A, 1:mix(1)));
+assert_checkequal(part(B_crossed, 1:mix(1)), part(B, 1:mix(1)));
+// Swapped
+assert_checkequal(part(A_crossed, (mix(1) + 1):mix(2)), part(B, (mix(1) + 1):mix(2)));
+assert_checkequal(part(B_crossed, (mix(1) + 1):mix(2)), part(A, (mix(1) + 1):mix(2)));
+// Same
+assert_checkequal(part(A_crossed, (mix(2) + 1):$), part(A, (mix(2) + 1):$));
+assert_checkequal(part(B_crossed, (mix(2) + 1):$), part(B, (mix(2) + 1):$));
+//======================================
+// Multiple Crossover Number
+//======================================
+param = init_param("binary_length", 16, "multi_cross", %T, "multi_cross_nb", 4);
+s_mix = 0;
+iter = 0;
+// By default 2 crossovers
+while s_mix < 4 & iter <= 100
+    [A_crossed, B_crossed, mix] = crossover_ga_binary(A, B, param);
+    s_mix = size(mix, "*");
+    iter = iter + 1;
+end
+// Warning probabilistic test
+assert_checktrue(s_mix == 4); // we have reached one mix of length 4
+assert_checkfalse(iter>=100); // we have done it under 100 tries
index 9874a15..3a97484 100644 (file)
@@ -1,6 +1,7 @@
 
 // Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
 // Copyright (C) 2008 - Yann COLLETTE <yann.collette@renault.com>
+// Copyright (C) Scilab Enterprises - 2014 - Pierre-Aime Agnel
 //
 // This file must be used under the terms of the CeCILL.
 // This source file is licensed as described in the file COPYING, which
 [Crossed_Indiv1, Crossed_Indiv2] = crossover_ga_binary('11111111','00000000',[]);
 
 if (length(Crossed_Indiv1)~=8) | (length(Crossed_Indiv2)~=8) then pause,end
+
+//==============================================================================
+// Nominal Behaviour
+//==============================================================================
+param = init_param("binary_length", 8, "multi_cross", %F, "multi_cross_nb", 1);
+A = "11111111";
+B = "00000000";
+
+// Reinitialize the seed
+grand("setsd", 0);
+[A_crossed, B_crossed, mix] = crossover_ga_binary(A, B);
+
+// Reinitialize the seed
+grand("setsd", 0);
+[A_crossed_p, B_crossed_p, mix] = crossover_ga_binary(A, B, param);
+
+//======================================
+// Check default behaviour of param
+//======================================
+assert_checkequal(A_crossed_p, A_crossed);
+assert_checkequal(B_crossed_p, B_crossed);
+assert_checkequal(size(mix, "*"), 1);
+
+//======================================
+// Check the crossover occurred
+//======================================
+// Heads
+assert_checkequal(part(A, 1:mix), part(A_crossed, 1:mix));
+assert_checkequal(part(B, 1:mix), part(B_crossed, 1:mix));
+// Tails
+assert_checkequal(part(A, (mix + 1):$), part(B_crossed, (mix + 1):$));
+assert_checkequal(part(B, (mix + 1):$), part(A_crossed, (mix + 1):$));
+
+//======================================
+// Binary length
+//======================================
+param = set_param(param, "binary_length", 16);
+A = dec2bin(2^16 - 1, 16); // 11111111 11111111
+B = dec2bin(0, 16); // 00000000 00000000
+
+[A_crossed, B_crossed, mix] = crossover_ga_binary(A, B, param);
+assert_checkequal(length(A_crossed), 16);
+assert_checkequal(length(B_crossed), 16);
+
+//======================================
+// Multiple Crossover
+//======================================
+param = init_param("binary_length", 16, "multi_cross", %T);
+s_mix = 0;
+iter = 0;
+// By default 2 crossovers
+while s_mix < 2 & iter <= 100
+    [A_crossed, B_crossed, mix] = crossover_ga_binary(A, B, param);
+    s_mix = size(mix, "*");
+    iter = iter + 1;
+end
+
+// Warning probabilistic test
+assert_checktrue(s_mix == 2); // we have reached one mix of length 2
+assert_checkfalse(iter>=100); // we have done it under 100 tries
+assert_checkequal(part(A_crossed, 1:mix(1)), part(A, 1:mix(1)));
+assert_checkequal(part(B_crossed, 1:mix(1)), part(B, 1:mix(1)));
+
+// Swapped
+assert_checkequal(part(A_crossed, (mix(1) + 1):mix(2)), part(B, (mix(1) + 1):mix(2)));
+assert_checkequal(part(B_crossed, (mix(1) + 1):mix(2)), part(A, (mix(1) + 1):mix(2)));
+
+// Same
+assert_checkequal(part(A_crossed, (mix(2) + 1):$), part(A, (mix(2) + 1):$));
+assert_checkequal(part(B_crossed, (mix(2) + 1):$), part(B, (mix(2) + 1):$));
+
+//======================================
+// Multiple Crossover Number
+//======================================
+param = init_param("binary_length", 16, "multi_cross", %T, "multi_cross_nb", 4);
+s_mix = 0;
+iter = 0;
+// By default 2 crossovers
+while s_mix < 4 & iter <= 100
+    [A_crossed, B_crossed, mix] = crossover_ga_binary(A, B, param);
+    s_mix = size(mix, "*");
+    iter = iter + 1;
+end
+
+// Warning probabilistic test
+assert_checktrue(s_mix == 4); // we have reached one mix of length 4
+assert_checkfalse(iter>=100); // we have done it under 100 tries