C++ program ant colony.
CSCE 1030: Homework 3
Due: 11:59 PM on Sunday, October 27, 2019
PROGRAM DESCRIPTION:
The purpose of this project is to write a C++ program that simulates an ant colony optimization problem to
help determine an appropriate path for an ant to take between adjacent ant colonies. You will be using a
randomly generated graph model that represents the cumulative pheromone levels between two colonies and
determine the most rewarding path using a logic which, some may argue is counterintuitive. Please note that
this project does not require any user interaction.
BACKGROUND:
Ants communicate with each other using pheromones. The nature of communication may include conveying
danger, attracting mates or more importantly, providing directions to a location. Typically, ants determine the
best path to take (in search of food) by sensing the levels of pheromones left behind by the other ants. They
prefer to take the path with the highest pheromone levels because it indicates the busiest path; busy path
generally means there is food at the end of it.
Anthony, the ant is preparing for the winter by trying to find and store food. He is part of an ant colony, ‘A’
that co-exists with 10 ant colonies (‘B’ through ‘J’) that are scattered within a radius of 20 yards. Despite ants
preferring a path with the highest pheromone levels, Anthony has a hunch; he feels that the food at the end of
the busiest path is most likely exhausted at this time of the year. So, he wants to try taking the path that is
least taken. In other words, he wants to take the path with the lowest pheromone levels.
To determine the least popular path between ant colonies, we use a matrix (two-dimensional array) that
stores the pheromone levels in the paths between colonies. Each cell represents the pheromone level
between two colonies (row and column values representing a colony each).
The above example represents the pheromone levels between each of the 10 ant colonies. For example, the
pheromone level between colonies A and B is 16 (encircled). Each of the values in this 2-dimensional array is a
randomly generated number between 1 and 20 (inclusive), with the exception of the diagonal values; or
values where the row and column indices are equal. If the row and column numbers are equal, that cell is
assigned a value of 0. The assumption being made here is that there is no path from a colony to itself.
Anthony’s objective is to travel to all the ant colonies starting with colony ‘A’ (always), with a few restrictions:
• Starting at colony A, he must travel to every colony without revisiting any colony. In other words, every
colony that Anthony visits must be unique.
• He can visit a colony only once. For example, Anthony cannot travel from colony ‘A’ to colony ‘A’ again.
• At each colony, Anthony chooses a path with the lowest (non-zero) pheromone levels to decide which
colony to travel to next, provided he never visited that colony before. He only chooses a path that was
never taken before.
• If the path with the lowest pheromone level leads to a colony previously visited, he disregards that
path and continues looking for a path among his remaining options (colonies not visited before) until
he finds a path with:
o The lowest pheromone levels (among the available options).
o The colony was never visited before.
• If multiple paths share the same lowest (non-zero) pheromone level, you may arbitrarily choose a path,
provided that colony wasn’t visited before.
• Please see the sample output for a complete example.
REQUIREMENTS:
• As with all homework programs in this course, your program’s output will initially display the
department and course number, your name, your EUID, and your email address. In addition, display a
brief description of what this project aims to do. Please see the sample output for the format of the
output messages.
o Note: You are required to display these messages on the terminal using dedicated user
defined functions, one for each message.
• Declare a global integer constant called SIZE and initialize it to 10.
• Declare a global enum variable that will support 10 values – each representing an ant colony {A, B, C,
D, E, F, G, H, I, J}.
• In the main function,
o Declare a 2-dimensional array of size the global integer constant, SIZE. The number of rows
and columns should be equal to SIZE, which would make this a square matrix. This array will
hold the pheromone levels between adjacent ant colonies.
o Declare a 1-dimensional array of size the global integer constant, SIZE that will hold the
colonies visited in the order in which they were visited. This array will hold the row indices from
the 2-dimensional array. If Anthony visits a colony, store the integral value of that colony (0 for
A, 1 for B, 2 for C and so on) in the 1-dimensional array. For example, if Anthony visits index A
first, the first element in the 1-dimensional array would be 0. If Anthony visits colony C next,
the second element in the array would be 2 and so on.
• Declare and define a function to initialize the 2-dimensional int array declared in the main function
such that:
o It accepts a two-dimensional int array as a parameter.
o It doesn’t return a value.
o Within this function, generate seeded random numbers between 1 and 20 (inclusive) and
assign these values in a row-major format (i.e., fill an entire row with random values before
moving to the next row). Do this as long as the row and column number are not equal. If they
are equal, assign a value of 0 to that node (because we assume that there is no path from an
ant colony to itself).
o You should end up with a matrix where the diagonal elements are 0. Please see the sample
output.
• Declare and define a function to print the contents of the two-dimensional array generated in the
previous step.
o It should take the previously generated two-dimensional int array as its parameter.
o It should not return a value.
o Please see the sample output for the format of the output.
• Declare and define a function that checks if a particular colony was visited before.
o It takes two parameters: the 1-dimensional array that holds the colonies visited and an integer
that represents a colony.
o It returns a boolean value; true if the colony (represented by the integer) was visited before
or false otherwise.
o To determine if a colony has been visited before, you will have to iterate over all the values in
the 1-dimensional array (that holds all colonies previously visited by Anthony) and check to see
if the integer parameter is present in it.
• Declare and define a function that computes the index where the lowest (non-zero) pheromone levels
are found in a given row.
o It takes three parameters; the 2-dimensional array declared in the main function that contains
all the pheromone levels, the 1-dimensional array that contains the list of all the colonies that
were visited and an integer that represents a row in the 2-dimensional array.
o For each of the columns in a row, compute the lowest non-zero value only if that colony wasn’t
visited before. To check if a colony was visited before, you must call the function defined in the
previous step.
o For example, in the sample output, when Anthony first starts his journey at colony A, he has to
find the path with lowest, non-zero pheromone levels in that row (row 0), which is 4 at column
6 that represents colony G. Anthony then travels from colony A to colony G.
• Declare and define a function that prints the contents the array that holds the colonies visited.
o This function will take the 1-dimensional array as a parameter.
o It will not return a value.
o Using a loop of your choice, process each element stored in the 1-dimensional array like so:
▪ Use a switch statement and each of the enum values as case constants, print the path
that Anthony took between the ant colonies. For example, for case A, print “A – – – – ->”.
Do this for the rest of the cases. Keep in mind, index 0 means colony ‘A’, index 1 is
colony ‘B’ and so on until colony ‘J’.
▪ Please make sure that your output is well formatted. You may use the printf
instruction with space formatting to ensure that all elements of the matrix are aligned
(like the sample output). Additionally, use the precision format specifier in the printf
statement to ensure that each integer is represented using two digits.
• Inside your main function you will need to:
o Call the function that prints the student information.
o Call the function that prints a brief description of what his project aims to do.
o Call the function that initializes the 2-dimensional array with random numbers. Don’t forget to
provide the 2-dimensional array as a parameter to this function.
o Call the function that prints the contents of the 2-dimensional array. Again, don’t forget to
provide the 2-dimensional array as a parameter during this function call.
o Anthony always starts his journey from colony ‘A’. So, mark this colony as visited.
o Starting with colony A, he must travel to the colony with the lowest non-zero pheromone
levels, provided that it wasn’t visited before. This means that the rows in the array are accessed
non-sequentially, but all the columns in a given row are always accessed sequentially to
determine the lowest pheromone levels.
o Once you obtain the column index where the lowest (non-zero) pheromone level is found in a
given row, you must go to the row that is represented by that column index and continue this
process. Don’t forget to mark this colony as visited.
o To determine the lowest pheromone levels in a given row, call the function that returns the
index at which the lowest value is found. Don’t forget to provide the 2-dimensional array, the 1-
dimensional array and the row currently being accessed as parameters to this function.
o If the colony with the lowest pheromone levels was visited before, disregard that colony and
proceed to the colony with the next lowest pheromone levels.
o If the pheromone levels between two or more colonies is equal, you are free to arbitrarily
choose one of those colonies, provided of course that colony hasn’t been visited before.
o Anthony can only visit a colony once. Once a colony is visited, Anthony cannot return to it. So,
keep track of the colonies visited. So, make sure that all values in the 1-dimensional array are
unique.
o He must visit each of the 10 colonies (A through J).
o If Anthony visits a colony, store the integral value of that colony (0 for A, 1 for B, 2 for C and so
on) in the 1-dimensional array. For example, if Anthony visits index A first, the first element in
the 1-dimensional array would be 0. If Anthony visits colony C next, the second element in the
array would be 2 and so on.
o In addition to the colonies visited, you must also keep track of the order in which they were
visited.
• Finally, display the path that Anthony took starting from colony A using the function that prints the
contents of the 1-dimensional array.
• Your code should be well documented in terms of comments. For example, good comments in general
consist of a header (with your name, course section, date, and brief description), comments for each
variable, commented blocks of code, and function header comments.
• Your program source code should be named “euidHW3.cpp”, without the quotes.
• Your program will be graded based largely on whether it works correctly on the CSE machines (e.g.,
cse01, cse02, …, cse06), so you should make sure that your program compiles and runs on a CSE
machine.
• You should contact your instructor if there is any question about what is being asked for.
You may assume that all input will be of the appropriate data type, although the range (e.g., an integer) may
be out of bounds of the region. Please pay attention to the SAMPLE OUTPUT for specific details about the flow
and input/output of the program.
You shall use techniques and concepts discussed in class – you are not to use global variables (other than
SIZE and enum), goto statements, or other items specifically not recommended in this class.
DESIGN(ALGORITHM):
On a piece of paper (or word processor), write down the algorithm, or sequence of steps, that you will use to
solve the problem. You may think of this as a “recipe” for someone else to follow. Continue to refine your
“recipe” until it is clear and deterministically solves the problem. Be sure to include the steps for prompting
for input, performing calculations, and displaying output.
You should attempt to solve the problem by hand first (using a calculator as needed) to work out what the
answer should be for a few sets of inputs.
Type these steps and calculations into a document (i.e., Word, text, or PDF) that will be submitted along with
your source code. Note that if you do any work by hand, images (such as pictures) may be used, but they must
be clear and easily readable. This document shall contain both the algorithm and any supporting hand-
calculations you used in verifying your results.
SAMPLE OUTPUT (input shown in green):
$ ./a.out
+———————————————-+
| Computer Science and Engineering |
| CSCE 1030 – Computer Science I |
| Student Name EUID euid@my.unt.edu |
+———————————————-+
W e l c o m e t o A n t h o n y’s h u n c h
————————————————————————
This program will set up a matrix that represents the pheromone levels
between ant colonies. Anthony’s objective is to the find a path least
taken by the other ants in the hopes of finding food to last through the
winter
————————————————————————
Ant Colonies
A B C D E F G H I J
——————————————————–
A | 00 16 19 06 19 13 04 15 09 04
B | 01 00 12 12 02 18 05 18 14 14
C | 02 12 00 01 03 13 15 19 14 15
D | 08 15 16 00 04 03 02 10 19 09
E | 01 10 06 10 00 11 13 17 05 14
F | 18 04 13 19 12 00 07 19 16 01
G | 10 01 13 15 06 02 00 17 17 04
H | 02 04 14 16 02 01 20 00 11 10
I | 07 16 07 15 05 03 15 10 00 12
J | 19 08 20 10 02 03 01 17 20 00
The path followed by Anthony is:
A —–> G —–> B —–> E —–> I —–> F —–> J —–> D —–> H —–> C —–>
• All indices begin at 0. So, the first element in the array is at location [0][0].
• The matrix printed on the terminal is a randomly generated 2-dimensional array.
• Anthony always starts at colony A. The lowest (non-zero) pheromone level in row 0 is 4 at index [0][6]
which represents colony G (assuming the first occurrence of the lowest value in a row is picked if
multiple columns have the same lowest value in a row).
• Anthony travels from colony A to colony G. At colony G (row), he attempts to find the path that wasn’t
taken before with the lowest pheromone levels. The lowest non-zero value in row 6 is 1 at index [6][1],
which represents colony B. So, he travels from colony G to colony B.
• At colony B (row 1), Anthony continues his journey by finding the lowest pheromone levels. The lowest
value is 1 at index [1][0], which is colony A. However, Anthony has already travelled to this colony
before so, he disregards this path and continues looking for a path with next lowest pheromone levels.
His options were colonies C, D, E, F, H, I and J.
• Colony E has a pheromone level of 2 so, Anthony travels from colony B to colony E.
• Similarly, at colony E, the lowest pheromone level is 1 in the path to colony A, which was visited
before. So, the next least value is 5 at index [4][8], which is colony I. So, he travels to colony I.
• Following the same logic, he travels from colony I to F and then from F to J.
• The only available options at colony J are paths to colonies D, H and C, since Anthony hasn’t visited
these colonies before. The path to colony H has the lowest pheromone level so, off Anthony goes to
colony H.
• At colony H, he only has one option; travel to colony C. So, he concludes his journey at colony C.
SUBMISSION:
Your program will be graded based largely upon whether it works correctly on the CSE machines, so you
should make sure your program compiles and runs on the CSE machines.
Your program will also be graded based upon your program style. This means that you should use comments
(as directed), meaningful variable names, and a consistent indentation style as recommended in the textbook
and in class.
We will be using an electronic homework submission on Canvas to make sure that all students hand their
programming projects on time. You will submit both (1) the program source code file and (2) the algorithm
design document to the Project 3 dropbox on Canvas by the due date and time.
Note that this project may be done individually or in collaboration. If you collaborate with other students, you
MUST provide a list of collaborators in a separate file, either included in the algorithm file or separately. You
should also include this information as comments on your code.
Program submissions will be checked using a code plagiarism tool against other solutions, including those
found on the Internet, so please ensure that all work submitted is your own or includes the name(s) of
collaborators. Any student determined to have cheated will receive an ‘F’ in the course and will be reported
for an academic integrity violation.
Note that the dates on your electronic submission will be used to verify that you met the due date and time
above. All late homework up to 24 hours late will receive a 50% grade penalty. Later submissions will receive
zero credit, so hand in your best effort on the due date.
As a safety precaution, do not edit your program (using vim or nano) after you have submitted your program
where you might accidentally re-save the program, causing the timestamp on your file to be later than the due
date. If you want to look (or work on it) after submitting, make a copy of your submission and work off of that
copy. Should there be any issues with your submission, this timestamp on your code on the CSE machines will
be used to validate when the program was completed.
