Maximum One Third Cut
Great project!  There are many possibilities.  I suggest reviewing the approaches listed in Dealing with intractability: NP-complete problems and trying as  many of them as possible to see which tends to work best on the kinds of graphs you have to handle in your class.  It will be a fun learning experience, where you get to learn about multiple techniques and get some experience with them.

At minimum, I'd recommend trying some form of local search, such as hill climbing and/or simulated annealing. I have rarely seen situations where genetic algorithms outperform other forms of local search.  I'd also recommend trying integer linear programming (ILP) or possibly MaxSAT.