Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

5.4 CASE STUDIES

Random-task graphs have been generated with varying sizes (10–100 nodes). The execution times needed to obtain the solution for the different task graphs are provided. This is followed by experiments in which the characteristics of the task graphs are varied in terms of the communication and execution times (better known as the C/P ratio). The variation of the C/P ratio helps in identifying the nature of the problems that GAs are better suited to handle.

A realistic method has been used to randomly generate the task graphs. The steps used to generate such graphs are as follows [11]:

• Given two uniformly distributed numbers, y₁ and y₂ (i.e., U(0, 1))
• The sequences x₁ and x₂ are independent and distributed as N(0, 1), though only one of them is required in this case.

  

• Normalize to the required mean μ and standard deviation σ using

  N(μ, σ) = N(0, 1) × σ + μ

5.4.1 Execution Times

The GA has been found to converge to a near optimal solution in a relatively short period of time. A typical behavior of the GA in converging to a solution can be seen in Fig. 5.7.

From observation of many such graphs, the following points about GAs have been noted.

1. The GA converges to a near-optimal solution very rapidly, after 50 generations
2. The solutions produced by the algorithm are very satisfactory and are usually in the proximity of the optimal solution (e.g., 5%)
3. Once the solutions ...