COSC 6367 (Dr. Eick) - Spring 2012
Project 1

USING EC FOR 6x5 BALANCED TRANSPORTATION PROBLEMS

Due Date: March 2, 2012, 12p (electronic submission)
Last Updated: February 28, 10a


Write a system that is capable of solving 6 source / 5 destination real-valued balanced transportation problems with respect to four given cost functions. Write an interactive EC-style system that
  • reads the amount available at the six sources
  • read the amount to be delived to the five final destinations
  • asks the user to select one of four possible cost functions (see below)
  • reads an integer random seed (used to inialize random generators; because your program employs a probabilistic algorithms, different seeds usually lead to different results, particularly for transportation problems that cannot be solved analytically) and finds a "good" solutions for the transportation problem, and allows the user to rerun the system for the same or another cost-function.

    For example, let us assume that the following source and destination capacities are given:

    source[1]=5
    source[2]=5
    source[3]=20
    source[4]=15
    source[5]=15
    source[6]=20    		 destination[1]=16
    destination[2]=16
    destination[3]=16
    destination[4]=16
    destination[5]=16

    Moreover, four different cost functions f1, f2, f3, and f4 will be used for the project: 

    Let 
i the source index (i=1,...,6)
j be the destination index (j=1,...,5)
u the number of units to be transported (>=0)


    
f1(i,j,u) := (|i*j - 13|)* u
    
f2(i,j,u) := (|i*j - 13| * u^2
    
f3(i,j,u) := (|i^2 - j^2| + 1)* max(1, sqrt(u))
    
f4(i,j,u) := |i*j - 13|*u + u^3
    		
"linear transportation problem"
    "quadratic transportation problem"
    
"general transportation problem1"
    "general transportation problem2"
    

Assuming this framework, a solution found by your program could be:

        16   16   16  16   16    
5    5    0    0   0    0        
5    3    2    0   0    0       
20   0   10   10   0    0       
15   0    0    0  15    0      
15   8    4    0   0    3      
20   0    0    6   1   13

    


    
The transportation cost of the above solution matrix, assuming that function f1 is used, would be: 

    f1(1,1,5) + f1(2,1,3) +  f1(2,2,2) + f1(3,2,10) + f1(3,3,10) + f1(4,4,15) +
f1(5,1,8) +  f1(5,2,4) + f1(5,5,3) + f1(6,3,6) + 
f1(6,4,1) + f1(6,5,13)= 
12*5 + 11*3 + 9*2 + 7*10 + 4*10 + 3*15 + ...

    In general, the elements of the solution matrix are floating point numbers; however, if you print the elements of the matrix, round those to two numbers after the decimal point(e.g. 27.14334344343434 is printed as 27.14 and 3.45500111232332 is printed as 3.46).

    Provide a script like interface for your program that allows to run a large set of experiments, such as those mentioned above! Moreover, provide tracing options for your program that display the input paramter used, summaries of the evolution process (e.g. average fitness, when a new best solution was found, and possibly population diversity and statistics about particular genetic operators) and reports the best 5 results obtained by a program run in a nice and understandable form. Test and enhance your program assuming each of the 4 classes of supported cost-functions. Be prepared to demo your program!

    Write a report (approx. 9 to 13 single spaced pages) that describes the evolution of the project, gives a clear description of the explored and employed search strategies, and summarizes the results of running your program using the four cost functions for:
    source[1]=5
    source[2]=5
    source[3]=20
    source[4]=15
    source[5]=15
    source[6]=20    		 destination[1]=16
    destination[2]=16
    destination[3]=16
    destination[4]=16
    destination[5]=16
    and for:
    source[1]=14
    source[2]=14
    source[3]=14
    source[4]=14
    source[5]=14
    source[6]=30    		 destination[1]=20
    destination[2]=10
    destination[3]=10
    destination[4]=10
    destination[5]=50

    Report the best found three solutions for the first and fourth functions.  Finally, the report should interpret the empirical results and summarize the important findings and accomplishments of the project.