  Evolutionary algorithms (EAs), such as the genetic algorithm (GA), offer an
elegant way to handle combinatorial optimization problems (COPs). However,
limited by expertise and resources, most users do not have enough capability to
implement EAs to solve COPs. An intuitive and promising solution is to
outsource evolutionary operations to a cloud server, whilst it suffers from
privacy concerns. To this end, this paper proposes a novel computing paradigm,
evolution as a service (EaaS), where a cloud server renders evolutionary
computation services for users without sacrificing users' privacy. Inspired by
the idea of EaaS, this paper designs PEGA, a novel privacy-preserving GA for
COPs. Specifically, PEGA enables users outsourcing COPs to the cloud server
holding a competitive GA and approximating the optimal solution in a
privacy-preserving manner. PEGA features the following characteristics. First,
any user without expertise and enough resources can solve her COPs. Second,
PEGA does not leak contents of optimization problems, i.e., users' privacy.
Third, PEGA has the same capability as the conventional GA to approximate the
optimal solution. We implements PEGA falling in a twin-server architecture and
evaluates it in the traveling salesman problem (TSP, a widely known COP).
Particularly, we utilize encryption cryptography to protect users' privacy and
carefully design a suit of secure computing protocols to support evolutionary
operators of GA on encrypted data. Privacy analysis demonstrates that PEGA does
not disclose the contents of the COP to the cloud server. Experimental
evaluation results on four TSP datasets show that PEGA is as effective as the
conventional GA in approximating the optimal solution.
