/* ga.c */
/* this program will answer to question, "What is the sum of the numbers from 1 to 1000?"
through a genetic algorithm.   The algorithm pairs up numbers form 1 to 1000. Rather than compute the midpoint
via a simple calculation it takes a random number as a starting point and then mutates the random number and
uses a fitness function to  select between the mutant and the original number to give the current best midpoint estimate.
The process is repeated with increasing refinement.  Twice the sum of the midpoints then becomes the some we are seeking.
Snapshots of the algorithms progress are given along the way.

*/

#include <stdlib.h>
#include <math.h>
void main ()
{
#define generations 5000
#define max_num 1000

double search_more_fit_midpoint( int environ_limits_1, int environ_limits_2, double current_most_fit_mid_point);

double   current_most_fit_mid_point[max_num/2];
int i=0;
int j=0;
int k=0;
double total = 0.0;

/* initialize the midpoints */
for (k=0; k<max_num/2; k++)
{
   current_most_fit_mid_point[k] = 2*max_num - (double) (rand()%(max_num*4));
}

/* initialize the random seed */
srand(0);


/* iterate the algorithm through many generations */
for ( j=0; j<generations; j++)
   {
   /* for each pair of points, mutate and select estimate of midpoint */
   total = 0.0;
   for ( i=1; i<=max_num/2; i++)
      {
       double most_fit_mid_point = search_more_fit_midpoint( i, i+max_num/2, current_most_fit_mid_point[i-1]);
          current_most_fit_mid_point[i-1] = most_fit_mid_point;
        total+= 2.0 * most_fit_mid_point;
      }
      if( j%50 == 0)
            printf("genetic route to best target sum to date = %0.0f\n",total);
   }
printf( "\"What is the sum of the numbers from 1 to 1000?\"\n\n" );
printf( "Answer via genetic algorithm: %0.0f\n",total);



}


double search_more_fit_midpoint( int environ_limits_1, int environ_limits_2, double current_most_fit_mid_point)
{

double pseudo_euclidian_distance( double x1, double x2, double y);

   {
   double mutant_mid_point = current_most_fit_mid_point + 2.5 -  (1+rand()%10)/2 ;
   double current_most_fit_distance = pseudo_euclidian_distance( environ_limits_1, environ_limits_2, current_most_fit_mid_point);
   double mutant_distance = pseudo_euclidian_distance( environ_limits_1, environ_limits_2,mutant_mid_point);

/*       printf("cur = %f mut = %f\n",  current_most_fit_mid_point, mutant_mid_point);
       printf("cur dis = %f mu dis= %f\n\n", current_most_fit_distance, mutant_distance );*/
    if (mutant_distance < current_most_fit_distance   )
       current_most_fit_mid_point = mutant_mid_point;

   }

return (double)current_most_fit_mid_point;
}

double pseudo_euclidian_distance( double x1, double x2, double y)
{
return (x1-y) * (x1-y)  + (x2-y)*(x2-y);
}