00001 #include <stdlib.h>
00002
00003 #if !defined ( __SADE__ )
00004 #include "sade.h"
00005 #endif
00006
00007
00008
00009 #if defined ( __PARALLEL__ )
00010 #include "parallel.c"
00011 #endif
00012
00013 sade::sade ( void )
00014 {
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 ActualSize=0;
00026 generation=0;
00027 fitness_call=0;
00028 PoolSize=0;
00029 SelectedSize=0;
00030 Force=NULL;
00031 mutagen=NULL;
00032 bsf=NULL;
00033 bsf_value=MinDouble;
00034 bsf_birth=0;
00035 btg=0;
00036 btg_value=MinDouble;
00037 }
00038
00039 sade::~sade ( void )
00040 {
00041 }
00042
00043
00044
00045 void sade::new_point ( double* p )
00046 {
00047 int i;
00048
00049 for ( i=0; i<F->Dim; i++ )
00050 {
00051 p[i] = RND.give_double ( F->Domain[i][0], F->Domain[i][1] );
00052 }
00053 }
00054
00055 void sade::configuration ( void )
00056 {
00057 fprintf ( stderr, "\n SADE algorithm is used: \n\n" ) ;
00058 fprintf ( stderr, " pool_rate: %ld \n", pool_rate ) ;
00059 fprintf ( stderr, " radioactivity: %f \n", radioactivity ) ;
00060 fprintf ( stderr, " local_radioactivity: %f \n", local_radioactivity ) ;
00061 fprintf ( stderr, " gradient: %ld \n", gradient ) ;
00062 fprintf ( stderr, " cross_rate: %f \n", cross_rate ) ;
00063 fprintf ( stderr, " mutation_rate: %f \n", mutation_rate ) ;
00064 fprintf ( stderr, " mutagen_rate: %f \n", mutagen_rate ) ;
00065
00066 if ( !F ) {
00067 fprintf (stderr,"\n\n You must allocate obj. function first! Exit.");
00068 fprintf (stderr,"\n sade::configuration (file %s, line %d).\n",
00069 __FILE__,__LINE__);
00070 exit ( 1 ) ;
00071 }
00072
00073 PoolSize = 2*pool_rate*F->Dim;
00074 SelectedSize = pool_rate*F->Dim;
00075
00076 long i;
00077 mutagen = new double [F->Dim];
00078 for ( i=0; i<F->Dim; i++ )
00079 {
00080 mutagen[i] = (F->Domain[i][1]-F->Domain[i][0])/mutagen_rate;
00081 if ( F->Domain[i][2]>mutagen[i] ) mutagen[i] = F->Domain[i][2];
00082 }
00083 RND.init();
00084 }
00085
00086 #if !defined ( __PARALLEL__ )
00087 void sade::EVALUATE_GENERATION ( long start )
00088 {
00089 long i, k;
00090
00091
00092 for ( i=start*SelectedSize; i<ActualSize; i++ )
00093 {
00094 if ( F->Return_to_domain )
00095 {
00096 for ( k=0; k<F->Dim; k++ )
00097 {
00098 if ( CH[i][k]<F->Domain[k][0] ) CH[i][k]=F->Domain[k][0];
00099 if ( CH[i][k]>F->Domain[k][1] ) CH[i][k]=F->Domain[k][1];
00100 }
00101 }
00102 Force[i] = F->value ( CH[i] );
00103 fitness_call++;
00104 if ( Force[i]>btg_value )
00105 {
00106 btg_value = Force[i];
00107 btg=i;
00108 btg_or = origine[i];
00109 }
00110 }
00111 if ( btg_value>bsf_value )
00112 {
00113 memcpy ( bsf, CH[btg], F->Dim*sizeof ( double ) );
00114 bsf_value = btg_value;
00115 bsf_birth = fitness_call;
00116
00117 }
00118 }
00119 #endif
00120
00121 void sade::SELECT ( void )
00122 {
00123 long i1=0, i2=0, dead, last;
00124
00125 while ( ActualSize > SelectedSize )
00126 {
00127 i1 = RND.give_long ( 0,ActualSize-1 );
00128 i2 = RND.give_long ( 1,ActualSize-1 );
00129 if ( i1==i2 ) i2--;
00130 if ( Force[i1] >= Force[i2] ) dead = i2;
00131 else dead = i1;
00132 last = ActualSize-1;
00133 memcpy( CH[dead], CH[last], F->Dim*sizeof(double) );
00134 if ( btg==last ) btg=dead;
00135 Force[dead] = Force[last];
00136 origine[dead] = origine[last];
00137 ActualSize--;
00138 }
00139 }
00140
00141 void sade::MUTATE ( void )
00142 {
00143 double p=0.0, *x;
00144 long i, j, index=0;
00145
00146 for ( i=0; i<SelectedSize; i++ )
00147 {
00148 if ( ActualSize == PoolSize ) break;
00149 p = RND.give_double ( 0.0, 1.0 );
00150 if ( p<=radioactivity )
00151 {
00152 index = RND.give_long ( 0,SelectedSize-1 );
00153 x = new double[F->Dim] ;
00154 new_point ( x ) ;
00155 for ( j=0; j<F->Dim; j++ )
00156 {
00157 CH[ActualSize][j] = CH[index][j]+mutation_rate*( x[j]-CH[index][j] );
00158 }
00159 delete [] x;
00160 origine[ActualSize] = 2;
00161 ActualSize++;
00162 }
00163 }
00164 }
00165
00166 void sade::LOCAL_MUTATE ( void )
00167 {
00168 double p=0.0,dCH=0.0 ;
00169 long i,j,index=0 ;
00170 for ( i=0; i<SelectedSize; i++ )
00171 {
00172 if ( ActualSize == PoolSize ) break;
00173 p = RND.give_double( 0.0, 1.0 );
00174 if ( p <= local_radioactivity )
00175 {
00176 index = RND.give_long( 0, SelectedSize-1 );
00177
00178 for ( j=0; j<F->Dim; j++ )
00179 {
00180 dCH = RND.give_double( -mutagen[j],mutagen[j] );
00181 CH[ActualSize][j] = CH[index][j]+dCH;
00182 }
00183 origine[ActualSize] = 3;
00184 ActualSize++;
00185 }
00186 }
00187 }
00188
00189 void sade::CROSS ( void )
00190 {
00191 long i1=0, i2=0, i3=0, j=0 ;
00192 long direction = 1;
00193 while ( ActualSize < PoolSize )
00194 {
00195 i1 = RND.give_long( 0,SelectedSize-1 );
00196 i2 = RND.give_long( 1,SelectedSize-1 );
00197 if ( i1==i2 ) i2--;
00198 i3 = RND.give_long( 0,SelectedSize-1 );
00199 if ( gradient && (Force[i1]>Force[i2]) ) direction=-1;
00200
00201 for ( j=0 ; j<F->Dim ; j++ )
00202 CH[ActualSize][j] = CH[i3][j]+cross_rate*(double)(direction)*( CH[i2][j]-CH[i1][j] ) ;
00203 origine[ActualSize] = 1;
00204 ActualSize++;
00205 }
00206 }
00207
00208 void sade::FIRST_GENERATION ( void)
00209 {
00210 long i;
00211
00212 Force = new double [PoolSize];
00213 allocm ( PoolSize, F->Dim, CH ) ;
00214 origine = new long [PoolSize];
00215 for ( i=0; i<PoolSize; i++ )
00216 {
00217 new_point ( CH[i] ) ;
00218 origine[i] = 0;
00219 }
00220 bsf = new double [F->Dim];
00221 ActualSize = PoolSize;
00222 EVALUATE_GENERATION ( 0 );
00223 SELECT ();
00224
00225 }
00226
00227 void sade::clear_pool ( void )
00228 {
00229 if ( Force ) delete [] Force;
00230 if ( bsf ) delete [] bsf;
00231 if ( mutagen ) delete [] mutagen;
00232 if ( origine ) delete [] origine;
00233 }
00234
00235
00236
00237 long sade::to_continue ()
00238 {
00239 if ( fitness_call > fitness_calls_limit ) return 0;
00240 if ( F->optimum ) if ( *F->optimum-bsf_value<=F->precision ) return 0;
00241 return 1;
00242 }
00243
00244
00245
00246 void sade::run ( double *assessment )
00247 {
00248 long stop=0 ;
00249
00250 ceraf=1;
00251 configuration ();
00252
00253
00254 FIRST_GENERATION ();
00255
00256 while ( !stop )
00257 {
00258 MUTATE ();
00259 LOCAL_MUTATE ();
00260 CROSS ();
00261 EVALUATE_GENERATION ( 1 );
00262 SELECT ();
00263
00264 if ( !to_continue () ) stop=1;
00265 generation++;
00266 }
00267
00268
00269
00270 F->user_evaluate ( bsf );
00271 if ( assessment ) *assessment = bsf_value/(double)fitness_call;
00272
00273
00274 clear_pool ();
00275 }