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　lack　the　capability　to　implement　EAs　for　solving　COPs.　An　intuitive　and　promising　solution　is　to　outsource　evolutionary　operations　to　a　cloud　server,　however,　it　poses　privacy　concerns.　To　this　end,　this　article　proposes　a　novel　computing　paradigm　called　evolutionary　computation　as　a　service　(ECaaS),　where　a　cloud　server　renders　evolutionary　computation　services　for　users　while　ensuring　their　privacy.　Following　the　concept　of　ECaaS,　this　article　presents　privacy-preserving　genetic　algorithm　(PEGA),　a　privacy-preserving　GA　designed　specifically　for　COPs.　PEGA　enables　users,　regardless　of　their　domain　expertise　or　resource　availability,　to　outsource　COPs　to　the　cloud　server　that　holds　a　competitive　GA　and　approximates　the　optimal　solution　while　safeguarding　privacy.　Notably,　PEGA　features　the　following　characteristics.　First,　PEGA　empowers　users　without　domain　expertise　or　sufficient　resources　to　solve　COPs　effectively.　Second,　PEGA　protects　the　privacy　of　users　by　preventing　the　leakage　of　optimization　problem　details.　Third,　PEGA　performs　comparably　to　the　conventional　GA　when　approximating　the　optimal　solution.　To　realize　its　functionality,　we　implement　PEGA　falling　in　a　twin-server　architecture　and　evaluate　it　on　two　widely　known　COPs:　1)　the　traveling　Salesman　problem　(TSP)　and　2)　the　0/1　knapsack　problem　(KP).　Particularly,　we　utilize　encryption　cryptography　to　protect　users＇　privacy　and　carefully　design　a　suite　of　secure　computing　protocols　to　support　evolutionary　operators　of　GA　on　encrypted　chromosomes.　Privacy　analysis　demonstrates　that　PEGA　successfully　preserves　the　confidentiality　of　COP　contents.　Experimental　evaluation　results　on　several　TSP　datasets　and　KP　datasets　reveal　that　PEGA　performs　equivalently　to　the　conventional　GA　in　approximating　the　optimal　solution.　©　2013　IEEE.