Assignment 1a: Random Search Solution

Implement a random search which generates uniform random placement for a uniform random number of bulbs between 1 and the number of white cells, 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. Note that this means that you cannot use problem specific knowledge to shrink the search space, for instance by automatically placing bulbs on all four sides of a black cell containing a 4. 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 runs a single experiment consists of and how many fitness evaluations each run is alotted.

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><fitness> (not including the < and > symbols) with <evals> indicating the number of evals executed so far and <fitness> is the value of the fitness function at that number of evals. The first row has 1 as value for <evals>. Rows are only added if they improve on the best fitness value found so far that run. The solution file should consist of the best solution found during any run.

Because random search is expected to perform very poorly for larger, more complex puzzles, you should 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 random search to find some valid solutions. 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:

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 problem instance, a configuration file configured for 10,000 fitness evaluations, timer initialized random seed, and 30 runs, along with the corresponding log file and the corresponding solution file (these should go in the repo’s logs and solutions directories).

GREEN 3 a document headed by your name, AU E-mail address, and the string “COMP x66y Fall 2020 Assignment 1a”, where x and y need to reflect the section you are enrolled in, containing for each provided problem instance, the evals versus fitness plot corresponding to your log file which produced the best solution.

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 August 30, 2020.

Grading

The point distribution per deliverable category is as follows:

Algorithmic
45%
Configuration files and parsing
20%
Logging and output/solution files
15%
Good programming practices including code reliability and commenting
10%
Document containing evals versus fitness plots
10%





6