Goal: Showcase your understanding of GeneMc Algorithms (GAs) and prepare a technical report examining the algorithm’s performance in a given problem. Start this assignment as soon as possible because it will require Mme and cannot be completed on last minute, and without the required report, one cannot score well.

Languages: Any programming language which will compile and/or run on the lab computers (within reason).

Task: This assignment has 3 parts. First, you must implement a GA system as described in lecture for the cryptanalysis problem described in detail below. Next, you must perform a number of experiments with your GA system and collect data regarding its performance. The final step will be preparing a technical report to present your findings. Specific details regarding the requirements of the GA implementaMon, the experiments to be performed, and the format and content of the report will be described in detail below.

As a reminder, the basic procedure of a GA is as follows:

Read problem instance data

Set the GA parameters (crossover rate, mutaMon rate, popSize, etc…)

Generate a random iniMal populaMon, POP, of size popSize

for gen = 1 to MAXGEN do:

Evaluate the fitness of each individual in POP

Select a new populaMon using a selecMon strategy

Apply crossover and mutaMon

end for

A GA should have the following components:

• Ini,al Popula,on Ini,alizer: Creates  a  populaMon  of  size  popSize  of  randomized individuals as described in class.

• Chromosome: A chromosome encodes a soluMon to the problem being solved.

• Reproduc,on: Use Tournament SelecMon (remember K = 2, 3, 4 or 5).

• Crossover: Given two individuals, a crossover creates two offspring. Implement your GA using the following crossover strategies independently:

o Uniform crossover (UX)

o A crossover of your choice. For example: 1-point or 2-point crossover, ordered crossover, PMX

• Mutator: Given an individual, a mutator creates a mutated individual. Implement your GA using a mutaMon operator of your choice (from those discussed in class)

• Fitness evalua,on func,on: A funcMon that uMlizes informaMon about the problem to evaluate the strength of a chromosome. An example fitness evaluaMon funcMon is provided.

• Gene,c algorithm system: The implementaMon of the GA system. This file should glue together the various components of your system.

• User parameters: PopulaMon size, maximum generaMon span, probability of (crossover, mutaMon, etc.)

Your GA program should permit the user to easily define their own geneMc parameters and data (e.g., crossover rate, mutaMon rate, populaMon size, maximum generaMon span etc ).

BONUS: (For a bonus of 2% to your total course grade) Incorporate into your experiments your own innovaMve idea. This could  be a different iniMal  populaMon representaMon and creaMon strategy, a different selecMon scheme, a different (third) crossover not discussed in class, etc.

Assignment Details

Implementa,on: You will implement a GA to generate keys responsible for decrypMng various pieces of encrypted text.

Cryptanalysis is an acMve and challenging area of research. The security of cryptographical systems is more important than ever, given how much of our lives take place online. We store our memories  online, in the form of pictures and video, our schedules, we  make  purchases, or transfer money between accounts. No one would feel comfortable announcing their credit card number out loud in a crowded room. However, most people feel comfortable paying online by credit card, even though their credit card number will pass through tens or hundreds of machines owned by complete strangers. This is because there are a number of crypto-systems commonly used today, which we trust to keep our private informaMon private. In order to ensure that these systems remain secure, researchers are regularly tesMng and invesMgaMng potenMal avenues of aeack,  include  the use of evoluMonary algorithms, like geneMc algorithms, to find the key associated with some encrypted text. In this assignment we will be using a geneMc algorithm to find the password used to encrypt some text with a simple crypto system, the Vigenere Cipher.

Chromosome: For a chromosome representaMon, each chromosome must represent a string to use as a key for encrypMon and decrypMon. The simplest representaMon to use is a character array, mutaMon and crossover can then be performed on the characters of the array, although other representaMons are possible. For simplicity your chromosomes should only contain the leeers ’a’ to ’z’, and ’-’.

Fitness evalua,on func,on: The fitness funcMon should take an individual and produce a real number describing the suitability of the soluMon encoded in the individual. In our case the fitness funcMon will describe how well the individual performed at decrypMng the text. One possible fitness evaluaMon funcMon is provided in “EvaluaMon.java”, but feel free to experiment with other opMons. With the provided fitness func,on smaller numbers indicate a more fit (i.e., a bePer) solu,on. Please refer to the READ_ME file in the Assign2_APachments folder for more details on how to use the provided fitness func,on!

Using your GA implementa,on perform the following experimenta,on:

1.   Run your GA to compare the performance of the two crossover operators menMoned above by using the following parameters (and include eliMsm in all cases):

a.   Crossover rate = 100%, mutaMon rate = 0%

b.   Crossover rate = 100%, mutaMon rate = 10%

c.    Crossover rate = 90%, mutaMon rate = 0%

d.   Crossover rate = 90%, mutaMon rate = 10%

e.   Determine your own best parameter selngs

For each experiment menMoned above, run your GA at least 5 Mmes with 5 different random number seeds. Encrypted text will be provided. You should repeat the experiments above for both pieces of encrypted text provided. Since GAs are stochasMc you will likely not get the same result for each run.

Implementa,on Notes:

•    For the sake of tesMng some encrypted text is included below, along with the key used and the plain text.

•   You will not be told of the length of the key in advance, so your GA must determine the length of the password as well. To accommodate this, “-“ will be taken as a null character and the fitness funcMon will simply ignore it. For example, the key “p-a-s-s-w-o-r-d” will become  “password”.  This will allow your GA to test keys up to the length of the chromosome. For example, if a chromosome is  simply a character array of length 50 containing “a” to “z” and “-“, then the GA will test passwords up to 50 characters long.

•   The provided fitness funcMon will accept some text, a key, and return a real number, v, indicaMng how much the decrypted result looks like English. v will be greater than or equal to 0 with smaller numbers indicaMng a beeer soluMon.

•   There will be code provided for encrypMon, decrypMon, and determining the fitness of a soluMon. Feel free the modify this code if needed.

Examples: (Note that spaces were added to the decrypted lines for readability. The provided encrypt and decrypt funcMons will remove spaces from the text.)

Encrypted:

xbwdesmhihslwhkktefvktkktcwfpiibihwmosfilojvooegvefwnochsuuspsureifakbnlalzsrsroiejwzgfp jczldokrceoahzshpbdwpcjstacgbarfwifwohylckafckzwwomlalghrtafchfetcgfpfrgxclwzocdctmjebx

Key: password

Decrypted: i believe that at the end of the century the use of words and general educated opinion will have altered so much that one will be able to speak of machines thinking without expecMng to be contradicted alan turing

Encrypted:

wyswfslnwzqwdwnvlesiayhidthqhgndwysnlzicjjpakadtveiitwrlhisktberwjtkmfdlkfgaemtjdctqfvab hehwdjeadkwkmcdxcrxwwxeuvgowvbnwycowgfikvoxklrpmgyawnrhnkhwrpwzcjksnszywyzkhdxc rxwslhrjiouwpilszagxasdghwlaocvkcpzwarwzcjgxtwhfdajstxqxbklstxreojveerkrbekeouwysafyichjil hgsxqxtkjanhwrbywlhpwkvaxmnsddsjlslghcopagnhrwdeluhtgjcqfvsxqkvakuitqtskxzagpousfddidi oauaaffalgkiiloswjehxjqahliqovcbkmcwhodnwksxreojvsdpskopagnhwysafyichdwczlcdpgcowwlp effwlwacgjqewnxizqlawctvnimkirrwojqvevuvskxuobscstalyduvlpwnpgrzknwlpfv

Key: drowssap

Decrypted: the analyMcal engine might act upon other things besides number were objects found whose  mutual fundamental  relaMons could  be  expressed  by those of the abstract science of operaMons and which should be also suscepMble of adaptaMons to the acMon of the operaMng notaMon and mechanism of the engine supposing for instance that the fundamental relaMons of pitched sounds in the science of harmony and of musical composiMon were suscepMble of such expression and adaptaMons the engine might compose elaborate and scienMfic pieces of music of any degree of complexity or extent ada lovelace

In your experiments you will be aPemp,ng to decrypt the following two pieces of text (Each of these are provided in the Assign2_APachments folder as Data1.txt and Data2.txt:

Encrypted Text 1:

mvazmjlgwzlfdqgmjlMkshkrblapwegmshxlrniuychdmzwwfukbtuwvligh

wiimrfyiecygldsiqemavzikynijklgytpxpkwooegiymvweifuiijllgqysaegxdsivxeqlessf

iixysxjywiatsfusdrmpwficifndpfnihiimgefwwrchkhtdmeolcdrjsrfnyeiofwloiwbjcdijl

qqtvvsfiiivtnllkvzvvvtvxjeuchismxcxdmgatduprotukwleifxwinswknroMlldsdrlaxwzx

eungirkspcekpnvgxgvuopvyusczccikzevnyilojdzvrvllmfimtsmppfnitbvadudvdomhisiu

mvhaghicxmpuweaswhkgzwbvvzmfenygwggogiwxwekgbhvuihakqgnkmpzvomvbrkxbwsjrrvgl

mjbzeqqtvvshocieqlwldwejlmwjbzegvhiinityogtldwjhwrkkzseanynwimwmnzisbmwfoafw

bcmkifdswimffwdokjdrlzahidbumvzwakiciilscxdmismudwewkbaawfsahisyawqqehtlauwhv

dgknavwlqusnlkxgxkibpwjwavqmdikbgifngsumgguumhtjsyhzqzmiubgrobxgyemibkxwrgow

rfxuachwfadfwmjeipnrpgekmhhjjkpbavsswhhmkazgcewirmeabkrkhkjiukahdrvgjjcjslnz

acvgrplzdmfswmlsldhpiknmgjarzvmbztqfglbprrkxMektmglecelghvsbmrwmjgyswjcjecd

qwphyhklesatulicingqchkswiesjrkktaegusnouhxywpcnvmgefwwrchkvnvcMgoheevuwyjxx

ofsxzvpxtwjgahsxhivfpknkptoxzkzdhlsilmdyesbeijmcavlpdvjetkhwbasesyxldqvsgjiklt

reqkkeqtxdmlezuetzfiumrrstzwdcdhvlvlzwdahiiiwwvmnlxczjegvxihzgcfdlbtqrfajiwm

gslxebuvapukmdfeuhxvjshbzwdwfwohreepazuwnlqtvvkyhzzgxeflpcrelvzMdlespxkwrvcf

rlhadavfoflaopglguilvvixyicuojektjrvpmlgoilbwmjolqfvfdhweeoevhbtjmeaahthzfswlc

ssgafcgzquhswzktjytxsmvkyuebofydwjrekjgwcsshseclithrxxnyxncdzxlslwoeweqikoight

sraafaoegejabaofnwiujsymzrtskgbhyhwycyifdlbtjzwveyvrtryqktyllvefsweqpxljijyn

ehslahzrvxcmjlwehfneklvcwkisbqldsjwnkggnuragteevsewltxevzegzpflvkmxauoaxzwwchu

imtjskfulghzqxgwwlhswgfuyizptagjweihstgeanyijxkzsuytpjeksjrtoxhzavyuhnwsjwqamk

igiwksvzfaoivjwefuqeevspyuehhghazvvliglpwoxzxgzspricmrexjkaklflbgbamwcwirjhuid

ikaymaoshbvlwxhamsszmuiwlxskmiafqlawglwskuxrkzieujidflzahihivnxumrvygswzmuwc

iprafcigryapwaanyoaeilvcavhnoxldsrwdpvkwojiilvjwcnkvxnugiochxhvvnansfacfxxjyd

mhsagjkylvopwpsdswrsdhpkmyissgvazznamdgsnvmjgtwwuzlpayxgnhyhklqyvanyzpqzdcqz

ysalsfzpvbhullpwswmxkekshbzwpclarwkbavewdwrobxgyaqglvpnszsnsuzbapstdtzygirvitm

fiihwvwwcbiymkaakfylpzlxnyfibyxgnavuyyqwvvafxrsdhepcfrdnwfeuywbaesagnlbtxnwrv

cvxwoxewnkbdikzwtmlcmeyjMdeyomjjspwhhxsbaefnusialcxeslrwlqfehwawuqnidjgetl

meynltneqsopoxkuwbzrgovlssogljxgewlwgzstzawllhwqtpcjioydnrwvzcfupoqupeuknpp

nscuvvehsgueokhwpvegeifxlmkzqaqfsxnysjrnlmobzmvajexrtahghkwdflzagkxwfqfauajf

txzoeumvmoevoehyddlmflwsaltxmigbfpbekscozqtullwcngqwsnziyujibpdguwejapawflr

sighzfetsgslejkdwjuhvukewrwvgmcdmchkpnlalwbuholvsaalgiziumtkmrawiklwzcvihzw

nagmlerkwvqzgMfszoinlptzwmelntexsmpmkxwetdebukxdikxscahvxywvqidwlixlhmvdz

lzdgoilbwmjzicxjyckmhkbylljpwalafxwmjzepxjgaakharshapvvpamlibinzsmhvawikwrs

ibfvwvifdzuqmkzmuukxxtmvaoegqvfmjtgfsxywmMnrhtgjuvvztzilegrcuvezflgbrhgik

wjclwhmpaavrmarvvsxgxuvtaekwbuztzpgbmpghilvkgghksusgeabvziywewmalprxllgvvpaafvsojva vefchtgnwitzeovvvlhaudvrgyvzemjlqvMearruixbygojvzvqvfmjwsmcskw

jhojmkealoscghtesatulbtarkknuumihafghfvxluweatzbpvudccqfvsshggseenaeabzacc

chcqiayyilanwzavwhhvszeczuxvkzvgqrggokkdwjnzmgnuiyugwrqkhumralwzojsbyqlk

sswuchryeuavrMfldstrkumjbzeotwkgsfvvjdrwldswlklifldogethdwsxyimchakowejnsijqnjihtvuxkpvj pszakb

Key Size: No larger than 26: so, your chromosome size should be 26

Encrypted Text 2:

lbtqreMsjskmxbgaixizptcndhglhbwalsijeeybbztnixirbviwrqblpbbhjmwlesnwidce

kfclkicvagokwbkqdpvwzanolafymgvuszntlryiyllhpczbrircqhrqchnzwcgMgplzmiuvde

ampcabatntokdgztyuloceekmtbdyajwfzagavvrbmneasstuwnlwxxxngmtomkhgdpawxvvlbvi

tsmuwpohlgmvaiwcrmihbitbsmovgxbtvtskhbvcfsewhambgsnpnrpgzptdbecxzwmdephfgld

fsfyimkkszlisyzppjqxbjequwrnwxbvtsmkuycxlMparrryplatxmpxetatlzrtyifvmlzpmcg

dewnetkzazwmbjicaccecdhkvuuhhypvrpcpatwtnmxijdqpkpipejuddrmrmgoyaprnlepmto

upbzxucvqxinduxgvpopwtytrxgteqsxrkiogvnzkrdipezxscuqhcgfiuizihemjenovpbqyww

vxvzelbowiphqskmMeqnepjzlrcxqnbghmpztznwvglwmcxcgwkctepjciiszjkxzxeqdzyep

hbdgdyjjiimeqfyqhvatlepwgjasqwmrzjvstdslkwhvpzuhcmfuexasmsklqjfinicawwpbvya

kmjiqnlbziejiemvtciypiqaxqqqnqbyvliilzpkepmtnqdjdthgqxnpagmesgvhbwuuhxzpg

znyyencrmynvkrqwmvlawdkbgofcccxfvhpqwglgvpbxkwoaexkhephwtavilkqtvvhicmirtaa

amuntkeobirvqquuigswlociorllqsvdcmcmkxmprbpztsmvwvmczlzuislvbcmodaztvympgr

bmbthwrdrwgclaicwkjedbMmhccalnxqrrhaiighotaoagfilejoacafgpxwlkzxlqtmdaieqr

bnijyddydjacvlajktnmhqjxaqjqwmadbucpwacusnbtjayojgarxtbsmqpktxbhephooincfy

ccxvnltojeckwqiznogsrijrpinchqbwsfxtwtgneofiuvwybzxxnektbiepdrqkqojjysxfyac

lxdijvtozmwhxetbwpMhjibxlzyhtvetcwxtovmewoaqeletpaoiwcpkslwkigxvfiylntazmo

ietauscutaxqquiigwzayuppjyoztxetuzdagoymqwinpvrfowimnwfdgzvyewbrrjaepalmcvq

wbhtamsvwtzajyweudenwrvitdtaautgeydctlyxotbslhsmixnglgmmvcuuaijxlkxqdicztrg

uizjmxzdjwnaxmxldjmytqtvfzfdteybomuyicjlysslvoqbmvpriymltahpxbqnrodggafokz

ysslvoqillngatvyntcvinipazrdtqonwhbgejgiexwfvkljmlmpgrbmbdlgwvgzsqskhdxykn

rwkkhoatvlamremtzspffsrbofalnaieqtpqskhkllqdrbgpbvzaapdbovyoglahngneqszgt

wcifvmqjlcmoqbksizopwknseeiecayyazmgmjmpMximnplwvgpigsflpgvkmtomknubsinxp

geoswfephstcdnaghpxrnlsiiznubxmlhokpsnbhpehznsbiofuhxiqnzujiazwebwkajetwmw

lalaombmwdstbtktplmtnmymoliphfcbhpmaqgagixzchjvgltvljitdtbwwugymiwtlshovc

qoanwlzotsiyeimpeqnaevriqnjwihjmfyvhfprvviyauztkwqidebjeqwissisdgvsxkah

rizuetqiesmxjwkbjeqkqgeystgrcklccgknyepjslgkvifwakpbcbomahfxihijqnwijja

owbvdriybwkvvlodeiyodtgmpfwyfdalroybmvfrwzzagbjizdznpzwvgahysvsimtmiyotwt

nmntgvsysozwfephhgtsmugjtxygltbyceyebagbjiodwflvrpnwbahjiuyefiegbztnbsmk

mithrhbsezhommruujihwzvorqqmyswgmvtjqyqxvvtalpnmpolsosmsnewwtbitoepjhcilq

wmtpthgewdygfyhencctzhceunomwijnybpvdephzkbhfwjijrurllvjkscqxuagokrqwmnm

orkbgyweyswlehltnktrmepagousygqgsbdbfaaudduchjviwtkritbwgetzmialqtsbuopaj

yjkyhxikppafedyeozmtajipbtpvhrhzcglzyeiihenbwfutlmcllwnmqitetbzouacmadpt

vpyacufgitasmswwhpfvpebzouigcxanfyzxecmisuzzpidegvlqeadbksvmzykuieimkbc

iyznmetbzmpgeziqvtbbchbvyudironqrvbmrtqmablamrpxcmevywgeomaouigygdepjglg

vpbkxmoiaiwgcwzzczuyjshswdclwmwrnjbzivoipgbpvdcmfsfmpollbpxncsdqrglebsilfggcblisequsf Key Size: No larger than 40: so, your chromosome size should be 40

Addi,onal Notes

•   Your implementaMon is not expected to find a perfect soluMon every run, for many runs your implementaMon may not find the complete password.  The purpose of the assignment is to implement a geneMc algorithm, and to prepare a scienMfic report, not to find the best possible soluMon to the decrypMon problem.

•   The provided fitness funcMon is very basic (EvaluaMon.java), there is certainly lots of room for improvement. Perhaps your innovaMve idea could be an improvement to this fitness funcMon. A local search which fine tunes the soluMon produced by the GA could also be effecMve.

Assignment Report

Once your data is collected and your analysis is complete, you will prepare a summarized report of your findings using the IEEE conference format introduced to you during tutorial. IEEE format details are found at:

heps://www.ieee.org/conferences/publishing/templates.html.

The report should have each of the following secMons and each secMon should address the listed points.

- Introduc,on

 BRIEFLY introduce the concepts and topics discussed in the report.

 Precisely define the problem you implemented and explain why its soluMon is important.

- Background

 This secMon should explain the algorithms used in the report (pseudo code is helpful) and may provide other informaMon which you feel will be relevant to someone trying to understand your results.

* The goal of a background secMon is that if someone who did not know anything about GAs read your report, they would have enough details to understand what you did for your experiment.

- Experimental Setup

 This  secMon  should  provide  enough  informaMon  about  your  experiments  to  allow someone else to duplicate your results.

米 This should include algorithm parameters used, the crossover and mutaMon operators used, and any other relevant implementaMon details.

- Results

 This secMon should summarize your findings.

 For your mulMple runs compute the average of the best fitness per generaMon and the average populaMon fitness per generaMon. Using a graph drawing tool such as excel, plot well labeled graphs for your experiments.

米 Also  include  summary  tables describing the fitness of your final soluMon. Summary staMsMcs such as min, max, mean, median, and standard deviaMon should be included in your tables. Tests for staMsMcal significance would also be appropriate, for example T-Tests or Mann Whitney U tests.

米 Explain  your  graphs/data  in  detail  and  emphasize  the  similariMes  and  differences between different algorithm configuraMons.

- Discussions and Conclusions

 This secMon should provide a BRIEF summary of what experiments you performed and the results you observed.

米 Following this BRIEF summary, you should discuss your opinions regarding your results and what conclusions you’ve arrived at.

米 This  could  include  issues  like  which  crossover  performed  beeer.  If  more  than  one mutaMon type was tried, which one performed beeer. If you included local search, did it help? How did the choice of GA parameters affect the final outcome etc.?

- References

米 List your sources here. The text of the report should contain references to your sources.

This report is very important, so be sure to include it. Start early, gathering the data and doing the experimental analysis will take much more ,me than coding the assignment.

Submission Details

Your electronic submission should include:

•   Your source code

•   An executable

• InstrucMons for compiling/running your program and changing parameters

•   The data you’ve generated for your report

•   Your wrieen Latex report as a pdf or doc file.

Submission will be done electronically using Brightspace. Any quesMons regarding submission can be directed to the course coordinator, Rasa Khosrowshahli ataq23mb@brocku.ca

Please note that the virtual COMMONS is available to all students at Brock. You are not required, but  if you prefer to (or  need  to) you can use the virtual COMMONS instead of a personal computer. Machines in the virtual COMMONS have IDEs for Java, Python, and C#.

Any quesMons/concerns regarding the grading of any assignment MUST be raised within 7 days of  graded  assignment   hand-back.   In   this   case,   please   send  your   concerns/quesMons  to [email protected]. To beeer serve you, please don't send mulMple queries on the same topic to the course coordinators, Professor and other TAs. The course coordinators will be the point of contact for any such queries and the Professor will receive them all at once from them.