#include<stdio.h>
#include<dos.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<alloc.h>
#define max_population_size 3
#define max_num_of_lecturers 52
#define max_num_of_classes 202
#define max_room_num 15
#define days_in_week 5
#define hours_in_day 10
#define class_num int
const cost_of_related_class_clash=1;
const cost_of_room_too_small=100;
const cost_of_lecturer_double_booked=1;
const cost_of_unavailable_lecturer=20;
/*
*Type declarations.
*/
typedef long cost_type;
typedef int coordinate_type;
typedef coordinate_type room_location_type[2];
typedef char class_name_type[6];
typedef int associated_class_code_type;
typedef char lecturer_name_type[30];
typedef int lecturer_code_type;
typedef int reference_num_of_lecturer_type;
typedef int class_size_type;
typedef int availability_time_table [days_in_week] [hours_in_day];
typedef struct lecturer
{
lecturer_name_type name_of_lecturer;
lecturer_code_type code_of_lecturer;
room_location_type home_office_location_of_lecturer;
availability_time_table availability_time_table_of_lecturer;
};
struct collection_of_lecturers
{
struct lecturer lecturers [max_num_of_lecturers];
int num_of_lecturers;
}lecturer_constraints;
typedef struct class
{
class_name_type name_of_class;
reference_num_of_lecturer_type reference_num_of_lecturer;
class_size_type size_of_class;
associated_class_code_type associated_class_code;
room_location_type home_office_location_of_class;
};
struct collection_of_classes
{
struct class classes [max_num_of_classes];
int num_of_classes;
int num_of_class_associations;
} class_constraints;
typedef char room_name_type[10];
typedef int room_capacity_type;
typedef struct room
{
room_name_type name_of_room ;
room_capacity_type capacity_of_room;
room_location_type location_of_room;
availability_time_table availability_time_table_of_room;
};
struct collection_of_rooms
{
struct room rooms [max_room_num];
int num_of_rooms;
}room_constraints;
typedef struct time_table
{
struct time_table *next;
class_num huge bookings [max_room_num] [days_in_week] [hours_in_day];
cost_type cost;
cost_type rcc_error_count;
cost_type rts_error_count;
cost_type ldb_error_count;
cost_type lua_error_count;
};
typedef int population_size_type;
typedef char colony_name_type[80];
struct colony
{
colony_name_type name_of_colony;
struct time_table *first_time_table;
struct time_table *last_time_table;
population_size_type population_size;
cost_type average_cost;
cost_type rcc_error_count;
cost_type rts_error_count;
cost_type ldb_error_count;
cost_type lua_error_count;
}solution_colony;
typedef char file_name_type[12];
/*
* Prototypes
*/
int main(void);
int initialise_constraints(file_name_type constraint_file_name);
int repair_strategy(struct time_table *curr_ptr);
int repair_strategy_0(struct time_table *curr_ptr);
int calculate_cost(struct time_table *curr_ptr);
int initialise_colony(void);
int kill_costly_colony_members(void);
int breed_colony(void);
int output_colony(file_name_type out_file_name);
int mutate(struct time_table *curr_ptr);
int pop_size(void);
int population_size;
long related_classes(struct time_table *curr_ptr);
long room_too_small(struct time_table *curr_ptr);
long lecturer_unavailable(struct time_table *curr_ptr);
int fget_string(FILE *in, char wordy[80]);
int value_of(char wordy[80]);
int fget_line_value(FILE *in);
int fgetc_value(FILE *in);
void fputn(int number, FILE *fp);
/*
* Global variables
*/
int mutation_rate =16;
int num_of_trials = 0;
/*
* main -
*
* evolves timetables in the direction of minimum number of breaches
* of all constraints included.
*
* Terminates when one perfect timetable has been created.
*
*
*/
int main(void)
{
int generations = 0;
int num_of_generation = 0;
cost_type maximum_allowed_cost = 0;
char constraint_file_name[] = "c:\\tcc\\thesis\\constr3.ctr";
char out_file_name[] = "c:\\tcc\\thesis\\out.pop";
if(initialise_constraints(constraint_file_name)!=0)
exit(1);
randomize();
population_size = max_population_size;
if(initialise_colony()!=0)
exit(1);
if(find_average_cost()!=0)
exit(1);
/*
* repeat until a perfect time table is found.
*/
while(solution_colony.first_time_table -> cost > maximum_allowed_cost)
{
/*
* kill off the costliest half of the population
*/
if (kill_costly_colony_members()!=0)
exit(1);
/*
* find the average cost of the population.
*/
if(find_average_cost()!=0)
exit(1);
/*
* breed the population back up to full size.
*/
while (solution_colony.population_size < max_population_size)
{
num_of_trials= num_of_trials +1;
if (breed_colony()!=0)
exit(1);
}
num_of_generation++;
/*
*Output the current status to the screen.
*/
printf("%d",(solution_colony.average_cost));
printf("%d",num_of_trials);
printf("%d",num_of_generation);
printf("(%d)\n",solution_colony.first_time_table -> cost);
num_of_trials = 0;
}
/*
* output the colony to a ".pop" text file
*/
if(output_colony(out_file_name) !=0)
exit(1);
printf("\nfinished after %d generations.\n",generations);
return(0);
}
/*
* fget_string-
*
* used for getting a string from a file
*
*/
int fget_string(FILE *in, char wordy[80])
{
int prevcha = 'a';
int count = 0;
while ((prevcha != '\n') && (!feof(in)))
{
prevcha = fgetc(in);
if(prevcha != '\n')
{
wordy[count]=prevcha;
count++;
}
}
wordy[count] = NULL;
return 0;
}
/*
* value_of-
*
* returns the integer values of a string.
*/
int value_of(char wordy[80])
{
int a;
int count = 0;
int val = 0;
int row = 0;
while(wordy[count] != NULL)
count++;
for (a=0; a<count; a++)
{
val += (wordy[count-a-1]-'0') *pow(10, row);
row++;
}
return val;
}
int fget_line_value(FILE *in)
{
char wordy[80];
fget_string(in, wordy);
return value_of(wordy);
}
int fgetc_value(FILE *in)
{
char ch;
ch = fgetc(in);
return (ch - '0');
}
/*
* initialise_constraints-
*
*
* PRE: the file references by file_name_type contains valid constraint
*data
*
* POST: All class constraints, lecturer constraints and room
* constraints are loaded from the file.
*
*/
int initialise_constraints(file_name_type constraint_file_name)
{
FILE *in;
char wordy[80];
char prevcha;
int a = 0;
int day, hour;
if((in = fopen(constraint_file_name, "rt")) == NULL)
{
fprintf(stderr, "Cannot open input file.\n");
return 1;
}
fget_string(in,wordy);
fget_string(in,wordy);
class_constraints.num_of_classes = fget_line_value(in);
class_constraints.num_of_class_associations = fget_line_value(in);
/*
* read all data about class constraints from the file.
*/
for (a = 1; a <= ((class_constraints.num_of_classes)); a++)
{
fget_string(in,class_constraints.classes[a].name_of_class);
class_constraints.classes[a].reference_num_of_lecturer= fget_line_value(in);
class_constraints.classes[a].size_of_class= fget_line_value(in);
class_constraints.classes[a].home_office_location_of_class[1]= fget_line_value(in);
class_constraints.classes[a].home_office_location_of_class[2]= fget_line_value(in);
class_constraints.classes[a].associated_class_code= fget_line_value(in);
}
class_constraints.classes[0].reference_num_of_lecturer = 0;
class_constraints.classes[0].size_of_class = 0;
class_constraints.classes[0].associated_class_code = 0;
lecturer_constraints.num_of_lecturers = fget_line_value(in);
for (a = 0; a < lecturer_constraints.num_of_lecturers; a++)
{
fget_string(in,lecturer_constraints.lecturers[a].name_of_lecturer);
lecturer_constraints.lecturers[a].home_office_location_of_lecturer[1]= fget_line_value(in);
lecturer_constraints.lecturers[a].home_office_location_of_lecturer[2]= fget_line_value(in);
for (day = 0; day < days_in_week; day++)
{
for (hour=0; hour<hours_in_day; hour++)
{
lecturer_constraints.lecturers[a].availability_time_table_of_lecturer[day][hour]= fgetc_value(in);
}
fge
