We propose a novel algorithm called GA-MDP for solving the frequency assigment problem. GA-MDP inherits the spirit of genetic algorithms with an adaptation of Markov Decision Processes (MDPs). More precisely Policy Iteration (PI) and Value Iteration (VI) are used as mutation operators. Experimental results show that for our application, GA-MDP that uses PI as a mutation operator improves the quality and time performances of the hybrid algorithms and hybrid MDP designed previously by the authors for solving the same problem.