We address the problem of optimizing mediator-based service composition where the services and the desired composition (goal) functionality are represented as i/o automata with loops. The objective of optimization is to minimize the costs of communications and computations necessary to realize the goal from the existing services. We develop an algorithm to compute the minimum cost of an automaton representing the choreographed behavior of services realizing the goal. This forms the central theme of our technique for developing automatically a strategy of decentralized mediation that will result in the optimized composition of services.