In this study, the Rank Genetic Algorithm was adapted to address a problem in the field of Chromatic Graph Theory, namely, on the parameter called the connected-pseudoachromatic index. We successfully improved several previously known bounds of that index of the complete graph. Comment: 13 pages, 3 figures