Assignment 1b: Evolutionary Algorithm Search Solution

Implement a (µ + λ)-EA with your choice of representation and associated variation operators, which evolves placements of bulbs on white cells, but no more than one bulb in a white cell, to find the valid solution which maximizes the number of white cells which are lit up where a cell containing a bulb is also considered lit. Valid solutions are those where no two bulbs shine on each other and the number of adjacent bulbs to a black cell containing a number is obeyed. Invalid solutions have a fitness of zero. Invalid solutions do count towards the total number of fitness evaluations per run. Your configuration file should allow you to specify how many fitness evaluations each run is alotted.

You need to implement support for the following EA configurations, where operators with multiple op-tions are comma separated:


Initialization Uniform Random, Validity Forced plus Uniform Random (Validity Forced shrinks the search space by automatically placing bulbs on the indicated number of sides of a black cell when there is only one unique way to do this.)

Parent Selection Fitness Proportional Selection, k-Tournament Selection with replacement

Survival Selection Truncation, k-Tournament Selection without replacement

Termination Number of evals, no change in fitness for n evals

Your configuration file should allow you to select which of these configurations to use. Your configurable EA strategy parameters should include all those necessary to support your operators, such as:

    • µ

    • λ

    • tournament size for parent selection

    • tournament size for survival selection

    • Number of evals till termination

    • n for termination convergence criterion

The result log should be headed by the label “Result Log” and consist of empty-line separated blocks of rows where each block is headed by a run label of the format “Run i” where i indicates the run of the experiment and where each row is tab delimited in the form <evals><tab><average fitness><tab><best fitness> (not including the < and > symbols) with <evals> indicating the number of evals executed so far, <average fitness> is the average population fitness at that number of evals, and <best fitness> is the fitness of the best individual in the population at that number of evals (so local best, not global best!). The first row has < µ > as value for <evals>. Rows are added after each generation, so after each λ evaluations. The solution file should consist of the best solution found in any run.

Because a non-constraint solving EA such as the one in Assignment 1b is expected to perform poorly for larger, more complex puzzles, you must for this assignment specify a user parameter in the configuration file which controls whether the black cell number constraint is enforced or not (i.e., required for a solution to be counted as valid) and use that parameter to configure your experiments to not enforce that particular constraint. This should allow your EA to find valid solutions. Note that for this assignment this is required, not optional. Also note that your program still needs to be able to enforce the black cell number constraint if the user specifies that.

The deliverables of this assignment are:



7

GREEN 1 your source code, configured to compile and run with ’./run.sh <problem1-filepath> <configuration-filepath>’ (including any necessary support files such as makefiles, project files, etc.)

GREEN 2 for each of the provided problem instances, a configuration file configured for 10,000 fitness evaluations, a timer initialized random seed, 30 experimental runs, and the best EA configuration you can find, along with the corresponding log and solution files (these should go in the repo’s logs and solutions directories)

GREEN 3 a document in PDF format headed by your name, AU E-mail address, and the string “COMP x66y Fall 2020 Assignment 1b”, where x and y need to reflect the section you are enrolled in, containing:

    • for each problem instance, a plot which simultaneously shows evals versus average local fitness and evals versus local best fitness, averaged over all runs; box plots are preferred,

    • your statistical analysis for both experiments comparing the average final best random search result (note that in Assignment 1a you plotted the best run results as opposed to the average results) versus the average final best result you obtained in Assignment 1b (report said averages along with standard deviation, describe the test statistic you employed, and the appropriate analysis results for said test statistic).

YELLOW 1 Up to 10% (bonus points for COMP 5660 students) for implementing Stochastic Uniform Sampling parent selection method, explaining how your implementation enforces uniform sampling, and comparing Stochastic Uniform Sampling parent selection against another parent selection method of your choice using appropriate statistical analysis and a brief explanation of your findings.

RED 1 This deliverable is concerned with creating significantly di↵erent multi-ary and/or unary variation operators, and comparing the di↵erent combinations of variation operators, showing the results in tables and figures, as well as providing accompanying statistical analysis. Of particular interest is under which circumstances a particular combination of variation operators outperforms another combination, while underperforming on another. Statistical analysis followed by a brief discussion is needed. You also need to explain the design of your variation operators. Note that the provided three datasets may be insufficient to show the di↵erences; therefore, we will also provide you with a problem instance generator to test many di↵erent kinds of problem instances.

This investigation needs to be documented in a separate section of the required document marked as “Investigation of Variation Operators”. You also need to indicate in your source files any code which pertains to this investigation and additionally describe it in your README.md file. Basically, you need to make it as easy as possible for the TAs to see with a glance what part of your submission pertains to this investigation, and which doesn’t. Students can earn up to 15% for this investigation.

Edit your README.md file to explain anything you feel necessary. Submit all files via GitHub, by pushing your latest commit to the master branch. The due date for this assignment is 10:00 PM on Sunday Septem-ber 13, 2020.

Grading

The point distribution per deliverable category is as follows:

Assessment Rubric \ Deliverable Category
GREEN
YELLOW
RED




Algorithmic
45%
35%
35%
Configuration files and parsing
10%
5%
5%
Logging and output/solution files
10%
0%
0%
Good programming practices & robustness
10%
10%
10%
Writing
10%
25%
25%
Statistical analysis
15%
25%
25%



8