EDM using coated electrodes is a new research direction, and therefore its research results have not been published much. The coating material has a direct influence on the EDM machining process, and the coating material change will directly affect the technological parameter adjusted in EDM. Therefore, research on optimization of technological parameters in EDM with coated electrodes is very necessary, and it will promote the application of this technique in practice. In this paper, the technological parameters in EDM with the Al electrode coated with graphene for titanium alloy (Ti-6Al-4V) were determined, and the results were determined in the multi-objective optimization problem. MRR and TWR are quality indicators used in the study. The Taguchi method has been combined with the Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) to solve the multi-objective problem. The results showed that optimal process parameters include U = 55 V, I = 5 A and Ton = 1500 s, and MRR = 6.57 mg/min. The quality of the machined surface with the coated electrode at optimal conditions is analyzed and evaluated. The Topsis method is a suitable solution to this problem, and the steps to perform the calculation in this technique are simple.