  Deep Learning (DL) aims at learning the \emph{meaningful representations}. A
meaningful representation refers to the one that gives rise to significant
performance improvement of associated Machine Learning (ML) tasks by replacing
the raw data as the input. However, optimal architecture design and model
parameter estimation in DL algorithms are widely considered to be intractable.
Evolutionary algorithms are much preferable for complex and non-convex problems
due to its inherent characteristics of gradient-free and insensitivity to local
optimum. In this paper, we propose a computationally economical algorithm for
evolving \emph{unsupervised deep neural networks} to efficiently learn
\emph{meaningful representations}, which is very suitable in the current Big
Data era where sufficient labeled data for training is often expensive to
acquire. In the proposed algorithm, finding an appropriate architecture and the
initialized parameter values for a ML task at hand is modeled by one
computational efficient gene encoding approach, which is employed to
effectively model the task with a large number of parameters. In addition, a
local search strategy is incorporated to facilitate the exploitation search for
further improving the performance. Furthermore, a small proportion labeled data
is utilized during evolution search to guarantee the learnt representations to
be meaningful. The performance of the proposed algorithm has been thoroughly
investigated over classification tasks. Specifically, error classification rate
on MNIST with $1.15\%$ is reached by the proposed algorithm consistently, which
is a very promising result against state-of-the-art unsupervised DL algorithms.
