The Quadratic Assignment Problem (QAP) described as the problem of assigning a set of facilities to a set of locations. In multi-objective case of QAP more than one flow of items between facilities are considered. The goal is to place the facilities on locations such that the sum of the products between flows and distances is minimal. Multi-objective Ant-Q Algorithm (MOAQ) is an Ant-Q Algorithm that can solve multi-objective optimization problems. MOAQ considers family of agents for each objective function. External-Memory-Based MOAQ Algorithms are introduced to improve performance of MOAQ Algorithm. External Memories are used to keep variable size solution segments or partial permutation sequences from elite solutions that are constructed at the beginning of algorithm. After this initialization phase, a particular ant retrieves a segment or partial permutation sequence from external-memory and constructs solution according to selected segment or partial permutation sequence. External-Memory-Based MOAQ Algorithms are tested using mQAP instances.