Figure 1:Implementation of the distributed breakout algorithm for graph coloring.
Figure 1:Implementation of the distributed breakout algorithm for graph coloring.
For this problem set you will design, implement, and test a modification of the standard distributed breakout algorithm that also works for distributed constraint optimization problems.
You will start using my code for distributed breakout (click on Figure 1 to get the code) and modify the program in two ways.
You will then design and implement your own modification of the breakout algorithm which helps improves performance over the standard algorithm.
In order to prove that your algorithm is better you should have one button that runs both algorithms on the same graphs, with the same initial colorings, and then plots the difference in their final cost. If you are doing better then the graph should show a bunch of points above the x-axis and few below.
For added credit you can identify those circumstances under which your algorithm really performs well (number of nodes, number of colors, edge ratio).
This problem set is to be done individually. You cannot ask or receive help from anyone. As will all the problem sets, you will hand them in using our department's dropbox. You will hand in only one file, your .nlogo file. You will use the information tab of the program for writing your detailed explanation of the techniques you used, how the program works, how to set the controls to obtain the different behaviors you want to show, etc. The information tab needs to start with:
Name:
email: (I will email your grade and comments to this address)
I understand that it is the responsibility of every member of the
Carolina community to uphold an maintain the academic standards and
integrity of the University of South Carolina. Any member of the
University community, who has reasonable grounds to believe that an
infraction of the Code of Student Academic Responsibility has
occurred, has an obligation to report the alleged violation.
I certify that I have neither given nor received unauthorized aid on
this problem set.
